2014
01-26

# There is a war

There is a sea.
There are N islands in the sea.
There are some directional bridges connecting these islands.
There is a country called Country One located in Island 1.
There is another country called Country Another located in Island N.
There is a war against Country Another, which launched by Country One.
There is a strategy which can help Country Another to defend this war by destroying the bridges for the purpose of making Island 1 and Island n disconnected.
There are some different destroying costs of the bridges.
There is a prophet in Country Another who is clever enough to find the minimum total destroying costs to achieve the strategy.
There is an architecture in Country One who is capable enough to rebuild a bridge to make it unbeatable or build a new invincible directional bridge between any two countries from the subset of island 2 to island n-1.
There is not enough time for Country One, so it can only build one new bridge, or rebuild one existing bridge before the Country Another starts destroying, or do nothing if happy.
There is a problem: Country One wants to maximize the minimum total destroying costs Country Another needed to achieve the strategy by making the best choice. Then what’s the maximum possible result?

There are multiple cases in this problem.
There is a line with an integer telling you the number of cases at the beginning.
The are two numbers in the first line of every case, N(4<=N<=100) and M(0<=M<=n*(n-1)/2), indicating the number of islands and the number of bridges.
There are M lines following, each one of which contains three integers a, b and c, with 1<=a, b<=N and 1<=c<=10000, meaning that there is a directional bridge from a to b with c being the destroying cost.
There are no two lines containing the same a and b.

There are multiple cases in this problem.
There is a line with an integer telling you the number of cases at the beginning.
The are two numbers in the first line of every case, N(4<=N<=100) and M(0<=M<=n*(n-1)/2), indicating the number of islands and the number of bridges.
There are M lines following, each one of which contains three integers a, b and c, with 1<=a, b<=N and 1<=c<=10000, meaning that there is a directional bridge from a to b with c being the destroying cost.
There are no two lines containing the same a and b.

4
4 0
4 2
1 2 2
3 4 2
4 3
1 2 1
2 3 1
3 4 10
4 3
1 2 5
2 3 2
3 4 3

0
2
1
3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 1<<30
#define maxn 110
#define maxm 20000
using namespace std;

int v[maxm],next[maxm],w[maxm];
int first[maxn],d[maxn],work[maxn],q[maxn];
int _v[maxm],_next[maxm],_w[maxm];
int src_set[maxn],sink_set[maxn];
int e,S,T,n,m;

void init(){
e = 0;
memset(first,-1,sizeof(first));
}

v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++;
v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++;
}

int bfs(){
int rear = 0;
memset(d,-1,sizeof(d));
d[S] = 0;q[rear++] = S;
for(int i = 0;i < rear;i++){
for(int j = first[q[i]];j != -1;j = next[j])
if(w[j] && d[v[j]] == -1){
d[v[j]] = d[q[i]] + 1;
q[rear++] = v[j];
if(v[j] == T)   return 1;
}
}
return 0;
}

int dfs(int cur,int a){
if(cur == T)    return a;
for(int &i = work[cur];i != -1;i = next[i]){
if(w[i] && d[v[i]] == d[cur] + 1)
if(int t = dfs(v[i],min(a,w[i]))){
w[i] -= t;w[i^1] += t;
return t;
}
}
return 0;
}

int dinic(){
int ans = 0;
while(bfs()){
memcpy(work,first,sizeof(first));
while(int t = dfs(S,INF))   ans += t;
}
return ans;
}

int main()
{
int kase;
scanf("%d",&kase);
while(kase--){
init();
scanf("%d%d",&n,&m);
S = 1,T = n;
for(int i = 0;i < m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
int maxflow = dinic();
for(int i = 0;i < e;i++){
_v[i] = v[i],_next[i] = next[i],_w[i] = w[i];
}
int src_cnt = 0,sink_cnt = 0;
for(int i = 2;i < n;i++){
if(d[i] != -1)  src_set[src_cnt++] = i;
else    sink_set[sink_cnt++] = i;
}
int ans = 0;
for(int i = 0;i < src_cnt;i++){
for(int j = 0;j < sink_cnt;j++){
for(int k = 0;k < e;k++)
v[k] = _v[k],next[k] = _next[k],w[k] = _w[k];
int tmp = dinic();
if(tmp > ans)   ans = tmp;
first[src_set[i]] = next[e-2];
first[sink_set[j]] = next[e-1];
e -= 2;
}
}
printf("%d\n",maxflow+ans);
}
return 0;
}

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)