【A* 网络流】codechef Chef and Cut
2024-09-28 04:52:05
高嘉煊讲的杂题;A*和网络流的练手题
题目大意
https://s3.amazonaws.com/codechef_shared/download/translated/SEPT16/mandarin/CHEFKC.pdf
一张有向带权图,固定$S$和$T$,求权值第$k$小的割。
$n \le 77,m\le 777,k \le 777$
题目分析
考虑如何描述每一种割:$p_i=1$表示$S$与$i$连通;$p_i=0$表示$i$与$T$连通。注意到这里的$\{p_i\}$与每种割是一一对应的,那么就可以以$p_i$为状态进行A*扩展求第$k$大状态。
接下去的问题就是如何计算$\{p_i\}$的权值。那么对于$p_i=1$,连边$(S,i,INF)$表示$(S,i)$无法割去;$p_i=0$同理。对于这张图做最小流即可。
最后可能是一个A*不同写法上的技巧。讲课时候讲的是一个状态$(len,\{p_i\},val)$表示只确认前$len$位的状态$p_i$的权值$val$。这种扩展是每次一步步确认元素,时空效率都不高。另一种写法直接$(len,\{p_i\},val)$表示$n$个点的状态为$\{p_i\}$,确定不改变 前$len$个元素,这个情况下的权值$val$。每次转移的时候,枚举新状态确认的长度$len'=len+1\cdots n$,保留前$len'-1$个状态并将$len'$位取反(这个处理是为了保证不重不漏遍历所有状态),然后以此状态处理出的最小割作为新的状态,这样就能保证省略很多中途步骤的无用状态而直接取当前状态的最优方案(因为既然要按顺序,那么必定从每个子状态的最优状态再进一步考虑)。
反正效率还不错,cc榜rk4.
1A还行
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = ;
const int maxm = ;
const int INF = 1e9; struct Edge
{
int u,v,f,c;
Edge(int a=, int b=, int c=, int d=):u(a),v(b),f(c),c(d) {}
}edges[maxm],sv[maxm];
struct node
{
int len,val;
bool a[maxn];
bool operator < (node a) const
{
return val > a.val;
}
void init(){memset(a, , sizeof a);}
}tmp,trans;
bool vis[maxn];
int n,m,k,S,T,sta,end;
int edgeTot,head[maxn],nxt[maxm],lv[maxn];
std::priority_queue<node> q; void addedge(int u, int v, int c)
{
edges[edgeTot] = Edge(u, v, , c), nxt[edgeTot] = head[u], head[u] = edgeTot, ++edgeTot;
edges[edgeTot] = Edge(v, u, , ), nxt[edgeTot] = head[v], head[v] = edgeTot, ++edgeTot;
}
bool buildLevel()
{
std::queue<int> q;
memset(lv, , sizeof lv);
q.push(S), lv[S] = ;
for (int tmp; q.size(); )
{
tmp = q.front(), q.pop();
for (int i=head[tmp]; i!=-; i=nxt[i])
{
int v = edges[i].v;
if (edges[i].f < edges[i].c&&!lv[v]){
lv[v] = lv[tmp]+, q.push(v);
if (v==T) return true;
}
}
}
return false;
}
int fndPath(int x, int lim)
{
if (!lim||x==T) return lim;
int sum = ;
for (int i=head[x]; i!=-&&sum < lim; i=nxt[i])
{
int v = edges[i].v, val = ;
if (lv[v]==lv[x]+&&edges[i].f < edges[i].c){
if ((val = fndPath(v, std::min(edges[i].c-edges[i].f, lim-sum)))){
sum += val, edges[i].f += val, edges[i^].f -= val;
}else lv[v] = -;
}
}
return sum;
}
int dinic()
{
int ret = , val = ;
while (buildLevel())
while ((val = fndPath(S, INF))) ret += val;
return ret;
}
void calc(node &x)
{
memset(head, -, sizeof head), edgeTot = ;
for (int i=; i<=m; i++) addedge(sv[i].u, sv[i].v, sv[i].c);
addedge(S, sta, INF), addedge(end, T, INF);
for (int i=; i<=x.len; i++)
if (x.a[i]) addedge(S, i, INF);
else addedge(i, T, INF);
std::queue<int> q;
x.val = dinic(), q.push(S);
memset(vis, , sizeof vis);
for (int i=; i<=n; i++) x.a[i] = ;
for (int tmp; q.size(); )
{
tmp = q.front(), q.pop();
for (int i=head[tmp]; i!=-; i=nxt[i])
if (edges[i].f < edges[i].c){
int v = edges[i].v;
if (!vis[v]) vis[v] = true, x.a[v] = , q.push(v);
}
}
}
int main()
{
freopen("CHEFKC.in","r",stdin);
freopen("CHEFKC.out","w",stdout);
scanf("%d%d%d%d%d",&n,&m,&k,&sta,&end), S = , T = n+;
for (int i=; i<=m; i++) scanf("%d%d%d",&sv[i].u,&sv[i].v,&sv[i].c);
tmp.len = , tmp.a[sta] = true, calc(tmp), q.push(tmp);
while (--k)
{
tmp = q.top(), q.pop();
for (int i=tmp.len+; i<=n; i++)
{
trans.init(), trans.len = i, trans.a[i] = !tmp.a[i];
for (int j=; j<i; j++) trans.a[j] = tmp.a[j];
calc(trans), q.push(trans);
}
}
printf("%d\n",q.top().val);
return ;
}
END
最新文章
- gulp 自动添加版本号
- 解决Maven工程中报 Missing artifact jdk.tools:jdk.tools:
- getAttribute、setAttribute、removeAttribute
- Fragment全解析系列(一):那些年踩过的坑
- 【树莓派】树莓派移动网络连接(配置4G网卡)
- window.document
- .NET(c#)new关键字的三种用法
- 神逸之作:国产快速启动软件神品ALTRun
- Careercup - Microsoft面试题 - 5684901156225024
- eclipse环境下tomcat远程调试方法
- windows进程中的内存结构(好多API,而且VC最聪明)
- JavaWeb核心编程之(三.4)Servlet Context 配置
- ie6,ie7,ie8 css bug汇总以及兼容解决方法
- Android 代码混淆
- 上传本地项目到githup仓库
- Shell 快速指南
- DALI解码模块
- Codeforces 776D The Door Problem
- Zookeeper 3、Zookeeper工作原理(转)
- Win8常用快捷键
热门文章
- CentOS下NFS服务器配置教程
- java实现连接mysql数据库单元测试查询数据项目分享
- output引用类型
- Visual Studio Code 入门教程
- Conferences
- 关于form的action路径填写
- mysql>; set sql_mode=&#39;&#39;; mysql>; set sql_mode=&#39;traditional&#39;;
- Chromium源码系列一:Chromium简介及源代码获取和编译
- 安装纯净 ubuntu linux (非虚拟机)
- April 30 2017 Week 18 Sunday