程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3395Special Fish 最“大”費用最大流

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

編輯：C++入門知識

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

求最大費用可以將邊權取負以轉化成求最小費用。然而此時依然不對，因為會優先尋找最大流，但是答案並不一定出現在滿流的時候。所以要加一些邊（下圖中的紅邊）使其在答案出現時滿流。設所有邊的流量為1，花費如下圖所示。顯然最大花費是1001，而沒有紅邊的情況下會得到3。

<喎?http://www.Bkjia.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; }