航空路线问题【网络流24题】

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary

思路

　　路径问题，首先拆点

　　标准路径问题网络流解法

　　只需要在S和1、2n和T之间连流量为2的边即可

　　ans就是 mincost - 2

　　最后用dfs枚举悔边输出路径

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 const int maxn = 1e5 +7;
  9 const int inf  = 0x3f3f3f3f;
 10 
 11 int n, m, s, t;
 12 int head[maxn],pre[maxn],inq[maxn],dis[maxn];
 13 int a[maxn];
 14 int cnt = 1;
 15 int path[2][maxn];
 16 int mincost = 0, maxflow = 0;
 17 struct edge {
 18     int u,to,nxt,w,c;
 19 }e[maxn << 1];
 20 int tot[5];
 21 
 22 template<class T>inline void read(T &res)
 23 {
 24     char c;T flag=1;
 25     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 26     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 27 }
 28 
 29 inline void BuildGraph(int u, int v, int w, int cost)
 30 {
 31     e[++cnt] = (edge){u, v, head[u], w,  cost}, head[u] = cnt;
 32     e[++cnt] = (edge){v, u, head[v], 0, -cost}, head[v] = cnt;///反向边
 33 }
 34 
 35 queue < int > q;
 36 
 37 bool SPFA(int x)
 38 {
 39     memset(inq, 0, sizeof(inq));
 40     for(int i = s; i <= t; i++) {
 41         dis[i] = inf;
 42     }
 43     q.push(x);
 44     dis[x] = 0;
 45     inq[x] = 1;
 46     while(!q.empty()) {
 47         int u = q.front();
 48         q.pop();
 49         inq[u] = 0;
 50         for(int i = head[u]; i; i = e[i].nxt) {
 51             int v = e[i].to, w = e[i].c;
 52             if(e[i].w > 0) {
 53                 if(dis[u] + w < dis[v]) {
 54                     dis[v] = dis[u] + w;
 55                     pre[v] = i;
 56                     if(!inq[v]) {
 57                         q.push(v);
 58                         inq[v] = 1;
 59                     }
 60                 }
 61             }
 62         }
 63     }
 64     if(dis[t] == inf)
 65         return 0;
 66     return 1;
 67 }
 68 
 69 void MCMF()
 70 {
 71     while(SPFA(s)) {
 72         int temp = inf;
 73         for(int i = pre[t]; i; i = pre[e[i].u]) {
 74             temp = min(temp, e[i].w);
 75         }
 76         for(int i = pre[t]; i; i = pre[e[i].u]) {
 77             e[i].w   -= temp;
 78             e[i^1].w += temp;
 79             mincost += e[i].c * temp;
 80             //printf("ans:%d\n",ans);
 81         }
 82         maxflow += temp;
 83     }
 84 }
 85 
 86 map<string, int> mp;
 87 string ss[200];
 88 
 89 void dfs(int x, int opt) {
 90     //cout << "x:" << x << endl;
 91     path[opt][++tot[opt]] = x;
 92     for ( int i = head[x]; i; i = e[i].nxt ) {
 93         int v = e[i].to;
 94         if(i & 1)
 95             continue;
 96         if(e[i ^ 1].w) {
 97             --e[i ^ 1].w;
 98             dfs(v, opt);
 99             return;
100         }
101     }
102 }
103 
104 
105 int main()
106 {
107     //freopen("data.txt", "r", stdin);
108     int vv;
109     read(n); read(vv);
110     s = 0, t = n << 1 | 1;
111     for( int i = 1; i <= n; ++i ) {
112         string _s;
113         cin >> _s;
114         mp[_s] = i;
115         ss[i] = _s;
116         BuildGraph(i, i + n, 1, -1);
117     }
118     BuildGraph(s, 1, 2, 0); BuildGraph(n << 1, t, 2, 0);
119     BuildGraph(1, 1 + n, 1, -1); BuildGraph(n, n << 1, 1, -1);
120     for( int i = 1; i <= vv; ++i ) {
121         string a, b;
122         cin >> a >> b;
123         int u = mp[a], v = mp[b];
124         if(u > v)
125             swap(u, v);
126         BuildGraph(u + n, v, inf, 0);
127     }
128     MCMF();
129     bool flag = 0;
130     // dbg(maxflow);
131     // dbg(-mincost);
132     if(!maxflow) {
133         puts("No Solution!");
134         return 0;
135     }
136     dfs(1, 0);
137     dfs(1, 1);
138     cout << -mincost - 2 << endl;
139     for ( int i = 1; i <= tot[0]; ++i ) {
140         if(path[0][i] >= 1 && path[0][i] <= n) {
141             cout << ss[path[0][i]] << endl;
142         }
143     }
144     //dbg(tot[1]);
145     for ( int i = tot[1]; i >= 1; --i ) {
146         if(path[1][i] >= 1 && path[1][i] <= n) {
147             if(!flag) {
148                 flag = 1;
149                 continue;
150             }
151             cout << ss[path[1][i]] << endl;
152         }
153     }
154     return 0;
155 }