[cpp]
*
hdu 3157
poj 3801
題意：一個電路板，上面有N個接線柱(標號1~N) 還有兩個電源接線柱 + -
然後是 給出M個部件正負極的接線柱和最小電流
求一個可以讓所有部件正常工作的總電流 沒有則輸出impossible
其實就是一個 有源匯 有上下界 最小流 問題
處理有源匯有上下界最大流問題是：
1.構造附加網絡
2.對ss、tt求最大流(ss、tt滿流則有解)
3.若有解，對s、t求最大流
而有源匯有上下界最小流問題則是：
1.構造附加網絡(不添加[t,s]邊)
2.對ss、tt求最大流
3.添加[t,s]邊
4.對ss、tt求最大流
5.若ss、tt滿流，則[t,s]的流量就是最小流
這個代碼大部分都是從別的題上摘過來的，注釋有點亂
*/
#include<stdio.h>
#include<string.h>
#define inf 0x7fffffff
struct edge//邊
{
int u,v,f,next,b,c;//邊的 前節點 後節點 可用流 下條邊的編號 原來邊上流的上下界
}e[1500];
int head[70],in[70],s,t,ss,tt,yong,sum;
int n,m;
void ini()
{
memset(head,-1,sizeof(head));
yong=0;
memset(in,0,sizeof(in));
s=0,t=n+1,ss=t+1,tt=ss+1;//各節點編號的安排
sum=0;
}
void adde(int from,int to,int xia,int shang)//加邊
{ //加邊
e[yong].u=from,e[yong].v=to,e[yong].f=shang-xia,e[yong].b=xia,e[yong].c=shang;
e[yong].next=head[from],head[from]=yong++;
//同時加它的退邊
e[yong].u=to,e[yong].v=from,e[yong].f=0,e[yong].b=xia,e[yong].c=shang;
e[yong].next=head[to],head[to]=yong++;
}
void build()
{
int i;
for(i=0;i<=t;++i)
{
if(in[i]>0)
adde(ss,i,0,in[i]);
else
{
adde(i,tt,0,-in[i]);
sum+=(-in[i]);
}
}
}
int d[1000],num[1000];
int min(int a,int b){return a<b?a:b;}
int sap_gap(int u,int f,int s,int t)//遞歸sap
{
if(u==t)
return f;
int i,v,mind=t,last=f,cost;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].v;
int flow=e[i].f;
if(flow>0)//參考模版寫的時候把flow寫成了f
{
if(d[u]==d[v]+1)
{
cost=sap_gap(v,min(last,flow),s,t);
e[i].f-=cost;
e[i^1].f+=cost;
last-=cost;
if(d[s]>=t+1)
return f-last;
if(last==0)
break;
}
if(d[v]<mind)
mind=d[v];
}
}
if(last==f)
{
--num[d[u]];
if(num[d[u]]==0)
d[s]=t+1;
d[u]=mind+1;
++num[d[u]];
}
return f-last;
}
int max_f(int s,int t)
{
int f=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for(num[s]=t+1;d[s]<t+1;)
f+=sap_gap(s,inf,s,t);
return f;
}
int main()
{
int i,dat,u,v,f1,f2,p;
char from[10],to[10];
while(scanf("%d%d",&n,&m),n+m)
{
ini();
for(i=1;i<=m;++i)
{
scanf("%s%s%d",from,to,&dat);
if(from[0]=='+') u=s;
else sscanf(from,"%d",&u);
if(to[0]=='-') v=t;
else sscanf(to,"%d",&v);
adde(u,v,dat,inf);
in[u]-=dat,in[v]+=dat;
}
build();
f1=max_f(ss,tt);
p=yong;
adde(t,s,0,inf);
f2=max_f(ss,tt);
if(f1+f2!=sum) printf("impossible\n");
else printf("%d\n",e[p^1].f);
}
return 0;
}
/*
hdu 3157
poj 3801
題意：一個電路板，上面有N個接線柱(標號1~N) 還有兩個電源接線柱 + -
然後是 給出M個部件正負極的接線柱和最小電流
求一個可以讓所有部件正常工作的總電流 沒有則輸出impossible
其實就是一個 有源匯 有上下界 最小流 問題
處理有源匯有上下界最大流問題是：
1.構造附加網絡
2.對ss、tt求最大流(ss、tt滿流則有解)
3.若有解，對s、t求最大流
而有源匯有上下界最小流問題則是：
1.構造附加網絡(不添加[t,s]邊)
2.對ss、tt求最大流
3.添加[t,s]邊
4.對ss、tt求最大流
5.若ss、tt滿流，則[t,s]的流量就是最小流
這個代碼大部分都是從別的題上摘過來的，注釋有點亂
*/
#include<stdio.h>
#include<string.h>
#define inf 0x7fffffff
struct edge//邊
{
int u,v,f,next,b,c;//邊的 前節點 後節點 可用流 下條邊的編號 原來邊上流的上下界
}e[1500];
int head[70],in[70],s,t,ss,tt,yong,sum;
int n,m;
void ini()
{
memset(head,-1,sizeof(head));
yong=0;
memset(in,0,sizeof(in));
s=0,t=n+1,ss=t+1,tt=ss+1;//各節點編號的安排
sum=0;
}
void adde(int from,int to,int xia,int shang)//加邊
{ //加邊
e[yong].u=from,e[yong].v=to,e[yong].f=shang-xia,e[yong].b=xia,e[yong].c=shang;
e[yong].next=head[from],head[from]=yong++;
//同時加它的退邊
e[yong].u=to,e[yong].v=from,e[yong].f=0,e[yong].b=xia,e[yong].c=shang;
e[yong].next=head[to],head[to]=yong++;
}
void build()
{
int i;
for(i=0;i<=t;++i)
{
if(in[i]>0)
adde(ss,i,0,in[i]);
else
{
adde(i,tt,0,-in[i]);
sum+=(-in[i]);
}
}
}
int d[1000],num[1000];
int min(int a,int b){return a<b?a:b;}
int sap_gap(int u,int f,int s,int t)//遞歸sap
{
if(u==t)
return f;
int i,v,mind=t,last=f,cost;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].v;
int flow=e[i].f;
if(flow>0)//參考模版寫的時候把flow寫成了f
{
if(d[u]==d[v]+1)
{
cost=sap_gap(v,min(last,flow),s,t);
e[i].f-=cost;
e[i^1].f+=cost;
last-=cost;
if(d[s]>=t+1)
return f-last;
if(last==0)
break;
}
if(d[v]<mind)
mind=d[v];
}
}
if(last==f)
{
--num[d[u]];
if(num[d[u]]==0)
d[s]=t+1;
d[u]=mind+1;
++num[d[u]];
}
return f-last;
}
int max_f(int s,int t)
{
int f=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for(num[s]=t+1;d[s]<t+1;)
f+=sap_gap(s,inf,s,t);
return f;
}
int main()
{
int i,dat,u,v,f1,f2,p;
char from[10],to[10];
while(scanf("%d%d",&n,&m),n+m)
{
ini();
for(i=1;i<=m;++i)
{
scanf("%s%s%d",from,to,&dat);
if(from[0]=='+') u=s;
else sscanf(from,"%d",&u);
if(to[0]=='-') v=t;
else sscanf(to,"%d",&v);
adde(u,v,dat,inf);
in[u]-=dat,in[v]+=dat;
}
build();
f1=max_f(ss,tt);
p=yong;
adde(t,s,0,inf);
f2=max_f(ss,tt);
if(f1+f2!=sum) printf("impossible\n");
else printf("%d\n",e[p^1].f);
}
return 0;
}作者：qq172108805
