首页 > 搜索 > DFS搜索 > hdu 2435 There is a war-DFS-[解题报告]C++
2014
01-26

hdu 2435 There is a war-DFS-[解题报告]C++

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

题意:给出一张n个点m条边的有向图。现在编号为1的城市想进攻编号为n的城市。n为了防御1的进攻,需要破坏一些道路使得1到n不连通,而破坏每条路都有一个代价,题目会告诉你。现在编号为1的城市想要让编号为n的城市花费尽量多的代价来破坏道路使得1到n不连通,因此他们可以在2-n中的任意城市间修一条无坚不摧的桥(这条桥既可以是原来存在的也可以是原来不存在的),问n花费的最大代价。

本来想先求一遍最小割,然后还原网络,把所有的割边的容量设为inf,求一遍最大流这样得到结果的。但是存在1到n不连通的情况,因此就不能求出最小割了。所以用到了一个更加暴力的方法。先求一遍最大流,得到maxflow,这是如果没有修桥的情况下的最小花费。然后枚举所有S所在的源集中的非S点a和T所在的汇集中的非T点b,假设他们之间的边被修成了不可摧毁的桥,这时候需要额外付出多少代价呢。答案就在残量网络里,就是从S到a的最小割与b到T的最小割中较小的那个。那就之间在a到b之间加一条cap=inf的边,然后从S到T跑最大流就可以了,得到答案ans。最后的答案就是maxflow+ans。

代码:

#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));
 }
 
 void add_edge(int a,int b,int c){
     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);
             add_edge(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];
                 add_edge(src_set[i],sink_set[j],INF);
                 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;
 }

 

 

解题转自:http://www.cnblogs.com/zhexipinnong/archive/2013/11/01/3402508.html


, ,
  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)