软件网站开发平台,个人网页设计首页,wordpress 白边,官网制作报价http://poj.org/problem?id2516 建图的时候 有个地方写错了 卡了半年。。 题意看了N久啊 有N个店主需要K种物品 有M个供应点 每个供应点有K种物品 其实是算K次最小费用 然后叠加 分解开来这题就是求把某种物品从供应点送到店主那里 多个源点-》多个汇点 所以加一个超级源点 和…http://poj.org/problem?id2516 建图的时候 有个地方写错了 卡了半年。。 题意看了N久啊 有N个店主需要K种物品 有M个供应点 每个供应点有K种物品 其实是算K次最小费用 然后叠加 分解开来这题就是求把某种物品从供应点送到店主那里 多个源点-》多个汇点 所以加一个超级源点 和 超级汇点 源点-M个供应点-N个店主-汇点 所以共有mn2条边 套最小费用模板就行了 View Code 1 #include iostream2 #includecstring3 #includecstdio4 #includealgorithm5 #includequeue6 #define MN 100007 #define MM 100008 #define INF 0xfffffff9 using namespace std;10 struct node11 {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 queueintq;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].capdist[v]dist[u]edge[i].cost)55 {56 dist[v] dist[u]edge[i].cost;57 //coutdist[v]endl;58 pp[v] i;59 if(!vis[v])60 {61 vis[v] 1;62 q.push(v);63 }64 }65 }66 }67 //coutdist[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,minc0;75 while(spfa(s,en,n))76 {77 minf INF1;78 for(i pp[en] ; i ! -1 ; i pp[edge[i].u])79 {80 if(edge[i].capminf)81 minf edge[i].cap;82 }83 flowminf;84 for(i pp[en] ; i ! -1 ; i pp[edge[i].u])85 {86 edge[i].cap-minf;87 edge[i^1].capminf;88 }89 mincminf*dist[en];90 }91 return minc;92 }93 int main()94 {95 int i,j,n,m,k,g;96 while(cinnmk)97 {98 if(n0m0k0)99 break;
100 int flag 0,ss0;
101 for(i 1; i n ; i)
102 for(j 1; j k ; j)
103 cinsh[i][j];
104 for(i 1; i m ; i)
105 for(j 1; j k ; j)
106 cinsto[i][j];
107 for(i 1;i k ; i)
108 for(j 1 ; j n ; j)
109 for(g 1; g m ; g)
110 cinco[i][j][g];
111 int s 0,en nm1;
112 for(i 1; i k ; i)
113 {
114 init();
115 int sa0;
116 for(j 1 ; j n ; j)
117 {
118 add(mj,en,sh[j][i],0);
119 sash[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,mg,INF,co[i][g][j]);
126 flow0;
127 ssmcmf(s,en,nm1);
128 if(saflow)
129 break;
130 }
131 if(ik1)
132 coutssendl;
133 else
134 cout-1\n;
135 }
136 return 0;
137 } 转载于:https://www.cnblogs.com/shangyu/archive/2013/03/21/2972399.html
