[第33届ACMICPC成都赛区网络赛 Problem H : There is a war]【最小割的一些性质】

【题目大意】
给定一个有向带权图。1为源点，n为汇点。
求加一条权为无穷的边，并且改边的起始点和结束点都1V<=100
E<=V*(V-1)/2
【算法分析】
暴力加边判断肯定不可行。
于是，我们可以弄一个稍微不暴力的方法。
先对这个图求一次最大流。得到一个最小割。
我们加的边一定是这样的：起始点在源集合，结束点在汇集合。
那么dfs求出源集。
设加的边是然后我们将发现，加了边以后，新的增广路必然是这样的：S->p1->p2….->a->b->p3…->T。
于是我们可以从a->b这里截断两边分别求解。
就是在一开始最小割的残余网络中，
若i∈源集，那么FF[i]=maxFlow (S->i)
若i∈汇集，那么FF[i]=maxFlow (i->T)
最终答案将是Max ( Min(FF[i],FF[j]) + initFlow ) 其中i∈源集，j∈汇集。initFlow为原图最小割。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=105;
struct edge{int x,y,c,next;}g[N*N],tg[N*N];
int n,m,e,S,T,Flow;
int ls[N],d[N],fa[N],cur[N],num[N],v[N],FF[N];

void addedge(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=e;
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=e;
}

void init(){
e=1; memset(ls,0,sizeof(ls));
scanf("%d%d",&n,&m);
int x,y,c,i;
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
}
}

void relabel(int k){
cur[k]=ls[k];
int mm=n;
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y] mm=d[g[t].y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[fa[i]^1].c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
for (i=1;i<=n;i++){
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
num[0]=n;
i=S;
while (d[S] int &t=cur[i];
for (;t;t=g[t].next)
if (g[t].c && d[g[t].y]+1==d[g[t].x]) break;
if (t){
fa[g[t].y]=t;
i=g[t].y;
if (i==T){
change();
i=S;
}
}
else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=g[fa[i]].x;
}
}
}

void dfs(int p){
v[p]=1;
for (int t=ls[p];t;t=g[t].next)
if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}

void solve(){
memset(v,0,sizeof(v));
dfs(1);
for (int i=2;i<=e;i++) tg[i]=g[i];
int initFlow=Flow,ans=Flow;
for (int i=2;i if (v[i]){
S=1; T=i;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
else{
S=i; T=n;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
for (int i=2;i for (int j=2;j if (v[i] && !v[j] && min(FF[i],FF[j])+initFlow>ans)
ans=min(FF[i],FF[j])+initFlow;
printf("%dn",ans);
}

int main(){
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=0;i init();
S=1; T=n; Flow=0;
sap();
solve();
}
return 0;
}