HDU 3395Special Fish 最“大”费用最大流 - c++编程基础

TOP

HDU 3395Special Fish 最“大”费用最大流

2015-07-20 18:04:29 来源: 作者: 【大中小】浏览:2次

求最大费用可以将边权取负以转化成求最小费用。然而此时依然不对，因为会优先寻找最大流，但是答案并不一定出现在满流的时候。所以要加一些边（下图中的红边）使其在答案出现时满流。设所有边的流量为1，花费如下图所示。显然最大花费是1001，而没有红边的情况下会得到3。

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 6000007 using namespace std; struct E { int u,v,Max,cost,next; }edge[200100]; int head[310]; int cur[310]; int Top; void Link(int u,int v,int w,int cost) { edge[Top].u = u; edge[Top].v = v; edge[Top].cost = cost; edge[Top].Max = w; edge[Top].next = head[u]; head[u] = Top++; } struct Q { int v; // bool operator < (const Q &a) const { // return a.cost < cost; // } }; void Updata(int site,int flow,int &cost) { for(int i = site;cur[i] != -1; i = edge[cur[i]^1].v) { edge[cur[i]].Max -= flow; edge[cur[i]^1].Max += flow; cost += edge[cur[i]].cost*flow; } } int dis[310]; int flow[310]; bool mark[310]; queue q; int Spfa(int S,int T,int n,int &cost) { while(q.empty() == false) q.pop(); memset(mark,false,sizeof(bool)*(n+2)); memset(dis,INF,sizeof(int)*(n+2)); memset(flow,INF,sizeof(int)*(n+2)); dis[S] = 0; Q f,t; f.v = S; dis[S] = 0; cur[S] = -1; mark[S] = true; q.push(f); while(q.empty() == false) { f = q.front(); q.pop(); mark[f.v] = false; for(int p = head[f.v]; p != -1; p = edge[p].next) { t.v = edge[p].v; if(edge[p].Max && dis[t.v] > dis[f.v] + edge[p].cost) { cur[t.v] = p; dis[t.v] = dis[f.v] + edge[p].cost; flow[t.v] = min(flow[f.v],edge[p].Max); if(mark[t.v] == false) { mark[t.v] = true; q.push(t); } } } } if(dis[T] != INF) { Updata(T,flow[T],cost); return flow[T]; } return 0; } int Cal_MaxFlow_MinCost(int S,int T,int n) { int f = 0,cost = 0,temp; do { temp = Spfa(S,T,n,cost); f += temp; }while(temp); printf("%d\n",-cost); return cost; } int val[110]; int main() { int n; int u,v,w,i,j,x; while(scanf("%d",&n) && n) { memset(head,-1,sizeof(int)*(2*n+3)); Top = 0; for(i = 1;i <= n; ++i) { scanf("%d",&val[i]); } int S = 1,T = 2*n+2; for(i = 1;i <= n; ++i) { Link(S,i+1,1,0); Link(i+1,S,0,0); Link(n+i+1,T,1,0); Link(T,n+i+1,0,0); Link(i+1,T,1,0); Link(T,i+1,0,0); } for(i = 1;i <= n; ++i) { for(j = 1;j <= n; ++j) { scanf("%1d",&x); if(x) { Link(i+1,j+n+1,1,-(val[i]^val[j])); Link(j+n+1,i+1,0,(val[i]^val[j])); } } } Cal_MaxFlow_MinCost(S,T,T); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：2014 Multi-University Training ..	下一篇：杭电 2015 偶数求和

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: