Our Journey of Xian Ends
链接：here
参考http://blog.csdn.net/wangshuhe963/article/details/78516821
如果不理解为什么这么建模可以先做下面那道题
费用流～
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int maxv = 40010; 5 const int maxe = 40010; 6 const int inf = 0x3f3f3f3f; 7 struct Edge{ 8 int head[maxv], nxt[maxe<<1], from[maxe<<1], to[maxe<<1], cap[maxe<<1], flow[maxe<<1], cost[maxe<<1]; 9 int cnt; 10 void init(){ 11 cnt = 0; 12 memset(head, -1, sizeof(head)); 13 } 14 void add(int u, int v, int cp, int cst){ 15 from[cnt] = u; 16 to[cnt] = v; 17 nxt[cnt] = head[u]; 18 cap[cnt] = cp; flow[cnt] = 0; cost[cnt] = cst; 19 head[u] = cnt++; 20 } 21 }; 22 struct MCMF{ 23 int n, m, s, t; 24 Edge e; 25 int inq[maxv], d[maxv], p[maxv], a[maxv]; 26 27 void init(int _n){ 28 n = _n; 29 e.init(); 30 } 31 void adde(int u, int v, int cap, int cost){ 32 e.add(u, v, cap, cost); 33 e.add(v, u, 0, -cost); 34 } 35 bool bellmanFord(int s, int t, int &flow, int &cost){ 36 for(int i = 0; i < n; i++) d[i] = inf; 37 memset(inq, 0, sizeof(inq)); 38 d[s] = 0; inq[s] = 1; p[s] = -1; a[s] = inf; 39 queue<int> q; 40 q.push(s); 41 while(!q.empty()){ 42 int u = q.front(); q.pop(); 43 inq[u] = 0; 44 for(int i = e.head[u]; ~i; i = e.nxt[i]){ 45 int v = e.to[i]; 46 if(e.cap[i] > e.flow[i] && d[v] > d[u] + e.cost[i]){ 47 d[v] = d[u] + e.cost[i]; 48 p[v] = i; 49 a[v] = min(a[u], e.cap[i] - e.flow[i]); 50 if(!inq[v]) q.push(v), inq[v] = 1; 51 } 52 } 53 } 54 if(d[t] == inf) return 0; 55 flow += a[t]; 56 cost += a[t] * d[t]; 57 int u = t; 58 while(u != s){ 59 e.flow[p[u]] += a[t]; 60 e.flow[p[u] ^ 1] -= a[t]; 61 u = e.from[p[u]]; 62 } 63 return 1; 64 } 65 int mincost(int s, int t){ 66 int flow = 0, cost = 0; 67 while(bellmanFord(s, t, flow, cost)); 68 if(flow == 3) return cost; 69 else return -1; 70 } 71 }solve; 72 int cnt; 73 map<string, int> mp; 74 int ID(char *s){ 75 if(!mp.count(s)) mp[s] = cnt++; 76 return mp[s]; 77 } 78 int main(){ 79 int t; 80 scanf("%d", &t); 81 while(t--){ 82 mp.clear(); 83 cnt = 0; 84 int n, m; 85 scanf("%d", &m); 86 n = m * 2; 87 solve.init(n * 2 + 2); 88 for(int i = 0; i < m; i++){ 89 char u[12], v[12]; 90 int w; 91 scanf("%s %s %d", u, v, &w); 92 int uu = ID(u), vv = ID(v); 93 solve.adde(uu + n, vv, inf, w); 94 solve.adde(vv + n, uu, inf, w); 95 } 96 int S = n * 2, T = n * 2 + 1; 97 map<string, int> ::iterator it; 98 for(it = mp.begin(); it != mp.end(); it++){ 99 int u = it->second; 100 if(it->first == "Xian"){ 101 solve.adde(u, u + n, 1, 0); 102 solve.adde(u + n, T, 1, 0); 103 }else if(it->first == "Qingdao"){ 104 solve.adde(u, u + n, 2, 0); 105 solve.adde(u + n, T, 2, 0); 106 }else if(it->first == "Hongqiao"){ 107 solve.adde(u, u + n, 2, 0); 108 solve.adde(S, u, 2, 0); 109 }else if(it->first == "Pudong"){ 110 solve.adde(u, u + n, 1, 0); 111 solve.adde(S, u, 1, 0); 112 }else{ 113 solve.adde(u, u + n, 1, 0); 114 } 115 } 116 solve.s = S; solve.t = T; 117 int ans = solve.mincost(S, T); 118 cout<<ans<<endl; 119 } 120 }
Our Journey of Dalian Ends
链接：here
基本是上面那个题的简化版，如果现场赛之前做过这道题，那上面那道应该没什么问题。
就是计算maxe的时候算错，总是忘记算拆点加入的边。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxv = 40010; 4 const int maxe = 40010; 5 const int inf = 0x3f3f3f3f; 6 int head[maxv], cnt; 7 struct Edge{ 8 int u, v, flow, cap, cost; 9 int nxt; 10 Edge(int u, int v, int flow, int cap, int cost, int nxt):u(u), v(v), flow(flow), cap(cap), cost(cost), nxt(nxt){} 11 Edge(){} 12 }e[maxe<<1]; 13 void add(int u, int v, int cap, int cost){ 14 e[cnt] = Edge(u, v, 0, cap, cost, head[u]); 15 head[u] = cnt++; 16 e[cnt] = Edge(v, u, 0, 0, -cost, head[v]); 17 head[v] = cnt++; 18 } 19 void init(){ 20 cnt = 0; 21 memset(head, -1, sizeof head); 22 } 23 int inq[maxv], d[maxv], p[maxv], a[maxv]; 24 int n, m; 25 26 bool bellmanFord(int s, int t, int &flow, int &cost){ 27 for(int i = 0; i < n * 2 + 2; i++) d[i] = inf; 28 memset(inq, 0, sizeof inq); 29 inq[s] = 1; d[s] = 0; p[s] = -1; a[s] = inf; 30 queue<int> q; 31 q.push(s); 32 while(!q.empty()){ 33 int u = q.front(); q.pop(); 34 inq[u] = 0; 35 for(int i = head[u]; ~i; i = e[i].nxt){ 36 int v = e[i].v; 37 if(e[i].cap > e[i].flow && d[v] > d[u] + e[i].cost){ 38 d[v] = d[u] + e[i].cost; 39 p[v] = i; 40 a[v] = min(a[u], e[i].cap - e[i].flow); 41 if(!inq[v]) { 42 q.push(v); 43 inq[v] = 1; 44 } 45 } 46 } 47 } 48 if(d[t] == inf) return 0; 49 int u = t; 50 flow += a[t]; 51 cost += a[t] * d[t]; 52 while(u != s){ 53 e[p[u]].flow += a[t]; 54 e[p[u] ^ 1].flow -= a[t]; 55 u = e[p[u]].u; 56 } 57 return 1; 58 } 59 int mincost(int s, int t){ 60 int flow = 0, cost = 0; 61 while(bellmanFord(s, t, flow, cost)); 62 if(flow == 2) return cost; 63 else return -1; 64 } 65 int id; 66 map<string, int> mp; 67 int ID(char *s){ 68 if(!mp.count(s)) mp[s] = id++; 69 return mp[s]; 70 } 71 72 int main(){ 73 int t; 74 scanf("%d", &t); 75 while(t--){ 76 init(); 77 id = 0; 78 mp.clear(); 79 scanf("%d", &m); 80 n = m * 2; 81 char s1[25], s2[25]; 82 int w; 83 for(int i = 0; i < m; i++){ 84 scanf("%s %s %d", s1, s2, &w); 85 int u = ID(s1), v = ID(s2); 86 add(u + n, v, inf, w); 87 add(v + n, u, inf, w); 88 } 89 int S = n * 2, T = n * 2 + 1; 90 map<string, int> :: iterator it; 91 for(it = mp.begin(); it != mp.end(); it++){ 92 int u = it->second; 93 if(it->first == "Shanghai"){ 94 add(S, u, 2, 0); 95 add(u, u + n, 2, 0); 96 }else if(it->first == "Xian" || it->first == "Dalian"){ 97 add(u + n, T, 1, 0); 98 add(u, u + n, 1, 0); 99 }else{ 100 add(u, u + n, 1, 0); 101 } 102 } 103 int ans = mincost(S, T); 104 cout<<ans<<endl; 105 } 106 }