福田网站建设龙岗网站建设,河南信阳网站建设公司电话,云网站 制作,wordpress模板大全1 /*若原图的基图不连通,2 或者存在某个点的入度或出度为 0 则无解。3 统计所有点的入度出度之差 Di, 对于 Di 0 的点,4 加边(s, i, Di, 0); 对于 Di 0 的点加边(i, t, -Di,0);5 对原图中的每条边(i, j),6 在网络中加边(i, j, ∞, Dij),Dij 为边(i, j)的权值。7 求一… 1 /*若原图的基图不连通,2 或者存在某个点的入度或出度为 0 则无解。3 统计所有点的入度出度之差 Di, 对于 Di 0 的点,4 加边(s, i, Di, 0); 对于 Di 0 的点加边(i, t, -Di,0);5 对原图中的每条边(i, j),6 在网络中加边(i, j, ∞, Dij),Dij 为边(i, j)的权值。7 求一次最小费用流,费用加上原图所有边权和即为结果。8 若进一步要求输出最小权值回路,则对所有流量 fij 0 的边(i, j),在原图中复制fij 份,这样原图便成为欧拉图,求一次欧拉回路即可。9 */10 #include iostream11 #include cstdio12 #include cstring13 #include queue14 #include algorithm15 #include cmath16 17 using namespace std;18 19 const int maxn 1e2 5;20 const int maxm 2e4 5;21 const int inf 0x3f3f3f3f;22 23 struct MCMF {24 struct Edge {25 int v, c, w, next;26 }p[maxm 1];27 int e, head[maxn], dis[maxn], pre[maxn], cnt[maxn], sumFlow, n;28 bool vis[maxn];29 void init(int nt){30 e 0, n nt 1;31 memset(head, -1, sizeof(head[0]) * (n 2));32 }33 void addEdge(int u, int v, int c, int w){34 p[e].v v; p[e].c c; p[e].w w; p[e].next head[u]; head[u] e;35 swap(u, v);36 p[e].v v; p[e].c 0; p[e].w -w; p[e].next head[u]; head[u] e;37 }38 bool spfa(int S, int T){39 queue int q;40 for (int i 0; i n; i)41 vis[i] cnt[i] 0, pre[i] -1, dis[i] inf;42 vis[S] 1; dis[S] 0;43 q.push(S);44 while (!q.empty()){45 int u q.front(); q.pop();46 vis[u] 0;47 for (int i head[u]; i 1; i p[i].next){48 int v p[i].v;49 if (p[i].c dis[v] dis[u] p[i].w){50 dis[v] dis[u] p[i].w;51 pre[v] i;52 if (!vis[v]){53 q.push(v);54 vis[v] 1;55 if (cnt[v] n) return 0;56 }57 }58 }59 }60 return dis[T] ! inf;61 }62 int mcmf(int S, int T){63 sumFlow 0;64 int minFlow 0, minCost 0;65 while (spfa(S, T)){66 minFlow inf 1;67 for (int i pre[T]; i 1; i pre[ p[i ^ 1].v ])68 minFlow min(minFlow, p[i].c);69 sumFlow minFlow;70 for (int i pre[T]; i 1; i pre[ p[i ^ 1].v ]){71 p[i].c - minFlow;72 p[i ^ 1].c minFlow;73 }74 minCost dis[T] * minFlow;75 }76 return minCost;77 }78 int ind[maxn], outd[maxn], ans ;79 bool build(int nt, int mt){80 init(nt);81 memset(ind, 0, sizeof(ind));82 memset(outd, 0, sizeof(outd));83 ans 0;84 int u, v, c;85 while (mt--){86 scanf(%d%d%d, u, v, c);87 u, v;88 addEdge(u, v, inf, c);89 ans c;90 outd[u], ind[v];91 }92 for (int i 1; i nt; i){93 if (ind[i] 0 || outd[i] 0) return false;94 }95 for (int i 1; i nt; i){96 if (ind[i] - outd[i] 0)97 addEdge(0, i, ind[i] - outd[i], 0);98 else if (ind[i] - outd[i] 0) 99 addEdge(i, n, outd[i] - ind[i], 0);
100 }
101 return true;
102 }
103 void solve(){
104 ans mcmf(0, n);
105 printf(%d\n, ans);
106 }
107 }my;
108 int main(){
109 int tcase, n, m;
110 scanf(%d, tcase);
111 while (tcase--){
112 scanf(%d%d, n, m);
113 if (!my.build(n, m)){
114 printf(-1\n);
115 continue;
116 }
117 my.solve();
118 }
119 return 0;
120 } 转载于:https://www.cnblogs.com/Missa/p/3273552.html
