| Ikki's Story I - Road Reconstruction
Description Ikki is the king of a small country – Phoenix, Phoenix is so small that there is only one city that is responsible for the production of daily goods, and uses the road network to transport the goods to the capital. Ikki finds that the biggest problem in the country is that transportation speed is too slow. Since Ikki was an ACM/ICPC contestant before, he realized that this, indeed, is a maximum flow problem. He coded a maximum flow program and found the answer. Not satisfied with the current status of the transportation speed, he wants to increase the transportation ability of the nation. The method is relatively simple, Ikki will reconstruct some roads in this transportation network, to make those roads afford higher capacity in transportation. But unfortunately, the country of Phoenix is not so rich in GDP that there is only enough money to rebuild one road. Ikki wants to find such roads that if reconstructed, the total capacity of transportation will increase. He thought this problem for a loooong time but cannot get it. So he gave this problem to frkstyc, who put it in this POJ Monthly contest for you to solve. Can you solve it for Ikki? Input The input contains exactly one test case. The first line of the test case contains two integers N, M (N ≤ 500, M ≤ 5,000) which represents the number of cities and roads in the country, Phoenix, respectively. M lines follow, each line contains three integers a, b, c, which means that there is a road from city a to city b with a transportation capacity of c (0 ≤ a, b < n, c ≤ 100). All the roads are directed. Cities are numbered from 0 to n − 1, the city which can product goods is numbered 0, and the capital is numbered n − 1. Output You should output one line consisting of only one integer K, denoting that there are K roads, reconstructing each of which will increase the network transportation capacity. Sample Input 2 10 1 1 Sample Output 1 Source , Ikki |
[] [Go Back] [] []
最小割的必须边。
1 #include2 #include 3 4 #define fread_siz 1024 5 6 inline int get_c(void) 7 { 8 static char buf[fread_siz]; 9 static char *head = buf + fread_siz; 10 static char *tail = buf + fread_siz; 11 12 if (head == tail) 13 fread(head = buf, 1, fread_siz, stdin); 14 15 return *head++; 16 } 17 18 inline int get_i(void) 19 { 20 register int ret = 0; 21 register int neg = false; 22 register int bit = get_c(); 23 24 for (; bit < 48; bit = get_c()) 25 if (bit == '-')neg ^= true; 26 27 for (; bit > 47; bit = get_c()) 28 ret = ret * 10 + bit - 48; 29 30 return neg ? -ret : ret; 31 } 32 33 inline int min(int a, int b) 34 { 35 return a < b ? a : b; 36 } 37 38 const int inf = 2e9; 39 const int maxn = 200005; 40 41 int n, m; 42 int s, t; 43 int edges; 44 int hd[maxn]; 45 int to[maxn]; 46 int fl[maxn]; 47 int nt[maxn]; 48 49 inline void add(int u, int v, int f) 50 { 51 nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++; 52 nt[edges] = hd[v]; to[edges] = u; fl[edges] = 0; hd[v] = edges++; 53 } 54 55 int dep[maxn]; 56 57 inline bool bfs(void) 58 { 59 static int que[maxn]; 60 static int head, tail; 61 62 memset(dep, 0, sizeof(dep)); 63 head = 0, tail = 0; 64 que[tail++] = s; 65 dep[s] = 1; 66 67 while (head != tail) 68 { 69 int u = que[head++], v; 70 for (int i = hd[u]; ~i; i = nt[i]) 71 if (!dep[v = to[i]] && fl[i]) 72 dep[v] = dep[u] + 1, que[tail++] = v; 73 } 74 75 return dep[t]; 76 } 77 78 int dfs(int u, int f) 79 { 80 if (u == t || !f) 81 return f; 82 83 int used = 0, flow; 84 85 for (int i = hd[u], v; ~i; i = nt[i]) 86 if (dep[v = to[i]] == dep[u] + 1 && fl[i]) 87 { 88 flow = dfs(v, min(f - used, fl[i])); 89 90 used += flow; 91 fl[i] -= flow; 92 fl[i^1] += flow; 93 94 if (used == f) 95 return f; 96 } 97 98 if (!used) 99 dep[u] = 0;100 101 return used;102 }103 104 inline bool dfs(void)105 {106 return dfs(s, inf) != 0;107 }108 109 inline void maxFlow(void)110 {111 while (bfs())112 while (dfs());113 }114 115 int dfn[maxn];116 int scc[maxn];117 118 void tarjan(int u)119 {120 static int low[maxn];121 static int stk[maxn];122 static int top, cnt, tim;123 124 stk[++top] = u;125 dfn[u] = low[u] = ++tim;126 127 for (int i = hd[u]; ~i; i = nt[i])if (fl[i])128 {129 if (!dfn[to[i]])130 tarjan(to[i]), low[u] = min(low[u], low[to[i]]);131 else if (!scc[to[i]])132 low[u] = min(low[u], dfn[to[i]]);133 }134 135 if (low[u] == dfn[u])136 {137 ++cnt; int t;138 do139 scc[t = stk[top--]] = cnt;140 while (t != u);141 }142 }143 144 inline void tarjan(void)145 {146 for (int i = 0; i < n; ++i)147 if (!dfn[i])tarjan(i);148 }149 150 inline void solve(void)151 {152 int ans = 0;153 154 for (int i = 0; i < edges; i += 2)if (!fl[i])155 {156 int u = to[i^1], v = to[i];157 if (scc[u] == scc[s])158 if (scc[v] == scc[t])159 ++ans;160 }161 162 printf("%d\n", ans);163 }164 165 signed main(void)166 {167 n = get_i();168 m = get_i();169 170 memset(hd, -1, sizeof(hd));171 172 for (int i = 1; i <= m; ++i)173 {174 int u = get_i();175 int v = get_i();176 int f = get_i();177 178 add(u, v, f);179 }180 181 s = 0, t = n - 1;182 183 maxFlow();184 185 tarjan();186 187 solve();188 }
@Author: YouSiki