bzoj 4464 : [Jsoi2013]旅行时的困惑
标签：反向 fine class print using min main 注意 microsoft
网络流建图。
从S向每个点连边，从每个点向T连边。
每条树边反向连一条下界为1，上界inf的边。
跑最小流。
注意加当前弧优化。
#include
#include
#define inf 0x3f3f3f3f
#define N 500005
#define M 5000005
using namespace std;
int head[N],ver[M],nxt[M],f[M],tot,ch[N],cur[M];
void add(int a,int b,int c)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;f[tot]=c;
tot++;nxt[tot]=head[b];head[b]=tot;ver[tot]=a;f[tot]=0;
return ;
}
int S,T,tim;
int vis[100005],q[M];
bool tell()
{
tim++;
int l=1,r=1;q[1]=S;
ch[S]=0;vis[S]=tim;
while(lr;i=nxt[i])
{
if(ch[ver[i]]==ch[a]+1&&f[i])
{
int t=zeng(ver[i],min(b-r,f[i]));
r+=t;f[i]-=t;f[i^1]+=t;
if(f[i]>0)cur[a]=i;
}
}
if(!r)ch[a]=-1;
return r;
}
int dinic()
{
int r=0,t;
while(tell())
{
for(int i=0;iru[i])
{
add(i,T,chu[i]-ru[i]);
}
else if(ru[i]>chu[i])
{
add(S,i,ru[i]-chu[i]);
}
}
dinic();
add(TT,SS,inf);
dinic();
printf("%d\n",f[tot]);
return 0;
}
bzoj 4464 : [Jsoi2013]旅行时的困惑
标签：反向 fine class print using min main 注意 microsoft
原文地址：http://www.cnblogs.com/ezyzy/p/7128538.html
评论