http://poj.org/problem?id=2516

建圖的時候 有個地方寫錯了 卡了半年。。

題意看了N久啊 有N個店主需要K種物品 有M個供應點 每個供應點有K種物品 其實是算K次最小費用 然后疊加 分解開來這題就是求把某種物品從供應點送到店主那里

多個源點-》多個匯點? 所以加一個超級源點 和 超級匯點 源點->M個供應點->N個店主->匯點 所以共有m+n+2條邊 套最小費用模板就行了

View Code 1 #include <iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<queue> 6 #define MN 10000 7 #define MM 10000 8 #define INF 0xfffffff 9 using namespace std; 10 struct node 11 { 12 int u,v,cost,cap,next; 13 }edge[MM]; 14 int head[MN],t,vis[MN],dist[MN],co[55][55][55],sh[55][55],sto[55][55],pp[MN],flow; 15 void init() 16 { 17 t = 0; 18 memset(head,-1,sizeof(head)); 19 } 20 void add(int u,int v,int c,int p) 21 { 22 edge[t].u = u; 23 edge[t].v = v; 24 edge[t].cap = c; 25 edge[t].cost = p; 26 edge[t].next = head[u]; 27 head[u] = t++; 28 edge[t].v = u; 29 edge[t].u = v; 30 edge[t].cap = 0; 31 edge[t].cost = -p; 32 edge[t].next = head[v]; 33 head[v] = t++; 34 } 35 int spfa(int s,int en,int n) 36 { 37 int i,j,u,v; 38 for(i =0 ; i <= n ; i++) 39 dist[i] = INF; 40 memset(vis,0,sizeof(vis)); 41 memset(pp,-1,sizeof(pp)); 42 queue<int>q; 43 q.push(s); 44 vis[s] = 1; 45 dist[s] = 0; 46 while(!q.empty()) 47 { 48 u = q.front(); 49 q.pop(); 50 vis[u] = 0; 51 for(i = head[u] ; i != -1 ; i = edge[i].next) 52 { 53 v = edge[i].v; 54 if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost) 55 { 56 dist[v] = dist[u]+edge[i].cost; 57 //cout<<dist[v]<<endl; 58 pp[v] = i; 59 if(!vis[v]) 60 { 61 vis[v] = 1; 62 q.push(v); 63 } 64 } 65 } 66 } 67 //cout<<dist[en]<<" "; 68 if(dist[en]==INF) 69 return 0; 70 return 1; 71 } 72 int mcmf(int s,int en,int n) 73 { 74 int i,minf,minc=0; 75 while(spfa(s,en,n)) 76 { 77 minf = INF+1; 78 for(i = pp[en] ; i != -1 ; i = pp[edge[i].u]) 79 { 80 if(edge[i].cap<minf) 81 minf = edge[i].cap; 82 } 83 flow+=minf; 84 for(i = pp[en] ; i != -1 ; i = pp[edge[i].u]) 85 { 86 edge[i].cap-=minf; 87 edge[i^1].cap+=minf; 88 } 89 minc+=minf*dist[en]; 90 } 91 return minc; 92 } 93 int main() 94 { 95 int i,j,n,m,k,g; 96 while(cin>>n>>m>>k) 97 { 98 if(n==0&&m==0&&k==0) 99 break; 100 int flag = 0,ss=0; 101 for(i = 1; i <= n ; i++) 102 for(j = 1; j <= k ; j++) 103 cin>>sh[i][j]; 104 for(i = 1; i <= m ; i++) 105 for(j = 1; j <= k ; j++) 106 cin>>sto[i][j]; 107 for(i = 1;i <= k ; i++) 108 for(j = 1 ; j <= n ; j++) 109 for(g = 1; g <= m ; g++) 110 cin>>co[i][j][g]; 111 int s = 0,en = n+m+1; 112 for(i = 1; i <= k ; i++) 113 { 114 init(); 115 int sa=0; 116 for(j = 1 ; j <= n ; j++) 117 { 118 add(m+j,en,sh[j][i],0); 119 sa+=sh[j][i]; 120 } 121 for(j = 1; j <= m ; j++) 122 add(s,j,sto[j][i],0); 123 for(j = 1; j <= m ; j++) 124 for(g = 1 ; g <= n ; g++) 125 add(j,m+g,INF,co[i][g][j]); 126 flow=0; 127 ss+=mcmf(s,en,n+m+1); 128 if(sa>flow) 129 break; 130 } 131 if(i==k+1) 132 cout<<ss<<endl; 133 else 134 cout<<"-1\n"; 135 } 136 return 0; 137 }

?

轉載于:https://www.cnblogs.com/shangyu/archive/2013/03/21/2972399.html

總結

以上是生活随笔為你收集整理的poj2516Minimum Cost的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。