生活随笔
收集整理的這篇文章主要介紹了
POJ 2135 最小费用最大流
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
思路：
源->1連費用0 流量2
其它的邊 費用w 流量1
n->匯 費用0 流量2
最小費用流 搞定~
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2010
#define M 201000
int n,m,first[N],next[M],v[M],edge[M],cost[M],tot,xx,yy,zz,S,T;
int vis[N],with[N],d[N],minn[N],ans;
void Add(
int x,
int y,
int C,
int E){edge[tot]=E,cost[tot]=C,v[tot]=y,next[tot]=first[x],first[x]=tot++;
}
void add(
int x,
int y,
int C,
int E){Add(x,y,C,E),Add(y,x,-C,
0);}
bool tell(){
memset(vis,
0,
sizeof(vis)),
memset(d,
0x3f,
sizeof(d));
memset(with,
0,
sizeof(with)),
memset(minn,
0x3f,
sizeof(minn));
queue<int>q;d[S]=
0;q.push(S);
while(!q.empty()){
int t=q.front();q.pop();vis[t]=
0;
for(
int i=first[t];~i;i=next[i])
if(d[v[i]]>d[t]+cost[i]&&edge[i]>
0){d[v[i]]=d[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]),with[v[i]]=i;
if(!vis[v[i]])vis[v[i]]=
1,q.push(v[i]);}}
return d[T]!=
0x3f3f3f3f;
}
int zeng(){
for(
int i=T;i!=S;i=v[with[i]^
1])edge[with[i]]-=minn[T],edge[with[i]^
1]+=minn[T];
return minn[T]*d[T];
}
int main(){
memset(first,-
1,
sizeof(first));
scanf(
"%d%d",&n,&m);S=n+
1,T=n+
2;
for(
int i=
1;i<=m;i++){
scanf(
"%d%d%d",&xx,&yy,&zz);add(xx,yy,zz,
1),add(yy,xx,zz,
1);}add(S,
1,
0,
2),add(n,T,
0,
2);
while(tell())ans+=zeng();
printf(
"%d\n",ans);
}
轉載于:https://www.cnblogs.com/SiriusRen/p/6532138.html
總結
以上是生活随笔為你收集整理的POJ 2135 最小费用最大流的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
