ZOJ 2760 How Many Shortest Path 最大流+floyd求最短路

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2760

题意：

给出一张有向带边权图，若不联通为-1。问不重叠的最短路有多少条(不重叠是指这条路上没有边重叠)。

思路：

首先由于源点和终点任意，设s为源点，t为终点。

所以用floyd求一遍最短路。

将所有可能是最短路的边建图。

设mp[i][j]为边的权值。dist[i][j]为i到j的最短路。

如果dist[s][i]+mp[i][j]+dist[j][t] == dist[s][t]，则i->j这条边就是最短路上的边。

设源点为s,汇点为t，连接图中所有可能是最短路上的边。容量为1。表示这条边只能经过一次。

然后求最大流。

要注意的是给出的图中可能点到该点本身的边权值不一定为0。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 int N;
  4 #define maxn 110
  5 const int inf = 0x3f3f3f3f;
  6 struct Edge
  7 {
  8     int from, to, cap, flow;
  9     Edge(int f, int t, int c, int fl)
 10     {
 11         from = f; to = t; cap = c; flow = fl;
 12     }
 13 };
 14 vector <Edge> edges;
 15 int s, t, n, m;
 16 vector <int> G[maxn];
 17 int vis[maxn], cur[maxn], d[maxn];
 18 void AddEdge(int from, int to, int cap)
 19 {
 20     edges.push_back(Edge(from, to, cap, 0));
 21     edges.push_back(Edge(to, from, 0, 0));
 22     m = edges.size();
 23     G[from].push_back(m-2);
 24     G[to].push_back(m-1);
 25 }
 26 bool bfs()
 27 {
 28     memset(vis, 0, sizeof(vis));
 29     d[s] = 0;
 30     vis[s] = 1;
 31     queue <int> q;
 32     q.push(s);
 33     while(!q.empty())
 34     {
 35         int u = q.front(); q.pop();
 36         for(int i = 0; i < G[u].size(); i++)
 37         {
 38             Edge &e = edges[G[u][i]];
 39             if(!vis[e.to] && e.cap > e.flow)
 40             {
 41                 vis[e.to] = 1;
 42                 d[e.to] = d[u]+1;
 43                 q.push(e.to);
 44             }
 45         }
 46     }
 47     return vis[t];
 48 }
 49 int dfs(int x, int a)
 50 {
 51     if(x == t || a == 0) return a;
 52     int flow = 0, f;
 53     for(int &i = cur[x]; i < G[x].size(); i++)
 54     {
 55         Edge &e = edges[G[x][i]];
 56         if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(e.cap - e.flow, a))) > 0)
 57         {
 58             e.flow += f;
 59             edges[G[x][i]^1].flow -= f;
 60             flow += f;
 61             a -= f;
 62             if(a == 0) break;
 63         }
 64     }
 65     return flow;
 66 }
 67 int MaxFlow()
 68 {
 69     int flow = 0;
 70     while(bfs())
 71     {
 72         memset(cur, 0, sizeof(cur));
 73         flow += dfs(s, inf);
 74     }
 75     return flow;
 76 }
 77 int mp[maxn][maxn];
 78 int dist[maxn][maxn];
 79 int main()
 80 {
 81     while(~scanf("%d", &N))
 82     {
 83         edges.clear();
 84         for(int i = 1; i <= N; i++) G[i].clear();
 85         for(int i = 1; i <= N; i++)
 86         {
 87             for(int j = 1; j <= N; j++)
 88             {
 89                 scanf("%d", &mp[i][j]);
 90                 dist[i][j] = mp[i][j];
 91                 if(i == j) dist[i][j] = mp[i][j] = 0;
 92             }
 93         }
 94 
 95         scanf("%d%d", &s, &t);
 96         s++; t++;
 97 
 98         if(s == t)
 99         {
100             printf("inf
"); continue;
101         }
102 
103         for(int i = 1; i <= N; i++)
104         for(int j = 1; j <= N; j++)
105         for(int k = 1; k <= N; k++)
106         {
107             if(dist[j][i] == -1 || dist[i][k] == -1) continue;
108             if(dist[j][k] == -1)
109             {
110                 dist[j][k] = dist[j][i] + dist[i][k];
111                 continue;
112             }
113             if(dist[j][k] >= dist[j][i] + dist[i][k])
114             {
115                 dist[j][k] = dist[j][i] + dist[i][k];
116             }
117         }
118         for(int i = 1; i <= N; i++)
119         {
120             if(dist[s][i] == -1) continue;
121             for(int j = 1; j <= N; j++)
122             {
123                 if(i == j) continue;
124                 if(dist[j][t] == -1) continue;
125                 if(dist[s][t] == -1) continue;
126                 if(dist[s][i] + mp[i][j] + dist[j][t] == dist[s][t])
127                 {
128                     AddEdge(i, j, 1);
129                 }
130             }
131         }
132         int flow = MaxFlow();
133         printf("%d
", flow);
134 
135 
136     }
137     return 0;
138 }