CF700C （枚举+tarjan）

Problem Break up （CF700C）

题目大意

　　给一张n个点，m条边的无向图，有边权，和起点S，终点T。 (n<=1000 , m<=30000)

　　要求最多割掉2条边，使得S到T不连通。

　　输出最小代价以及方案。

解题分析

　　如果只是割掉1条边，那么就是求割边了。

　　如果要割掉2条边，一个自然的思路就是枚举一条边后再求割点，这样复杂度是O（m ^2）的，显然会超时。

　　再考虑并不需要枚举每一条边，只需要求一条S到T的路径，枚举这条路径上的边即可。因为若要不连通，必定要割掉这条路径上的某一条边

　　复杂度O（n*m）。

参考程序

  1 #include <map>
  2 #include <set>
  3 #include <stack>
  4 #include <queue>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <string>
  8 #include <vector>
  9 #include <cstdio>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 #pragma comment(linker,"/STACK:102400000,102400000")
 15 using namespace std;
 16 
 17 #define     N             100008             
 18 #define     V             1008
 19 #define        E            60008    
 20 #define        lson        l,m,rt<<1
 21 #define     rson        m,r+1,rt<<1|1
 22 #define        clr(x,v)    memset(x,v,sizeof(x));
 23 #define        LL            long long 
 24 
 25 const int    mo    =    1000000007;
 26 const int     inf =    0x3f3f3f3f;
 27 const int     INF =    2000000008;
 28 /**************************************************************************/ 
 29 
 30 int n,m,S,T,tmp;
 31 int vis[V],path[V],dfn[V],low[V],road[V],bridge[E];
 32 int ans;
 33 int ANS[V];
 34 struct line{
 35     int u,v,w,nt;
 36 }eg[E];
 37 int sum,lt[V];
 38 
 39 
 40 void adt(int u,int v,int w){
 41     eg[++sum]=(line){u,v,w,lt[u]};
 42     lt[u]=sum;
 43 }
 44 void add(int u,int v,int w){
 45     adt(u,v,w); adt(v,u,w);
 46 }
 47 
 48 bool dfs(int u){
 49     vis[u]=1;
 50     if (u==T) return true; 
 51     for (int i=lt[u];i;i=eg[i].nt){
 52         int v=eg[i].v;
 53         if (vis[v]) continue;
 54         if (dfs(v)){
 55             path[++path[0]]=i/2;
 56             return true;
 57         }
 58     }
 59     return false;
 60 }
 61 
 62 bool dfs_2(int u,int del){
 63     vis[u]=1;
 64     if (u==T) return true;
 65     for (int i=lt[u];i;i=eg[i].nt){
 66         int v=eg[i].v;
 67         if (i/2==del) continue;
 68         if (vis[v]) continue;
 69         if (dfs_2(v,del)){
 70             road[++road[0]]=i/2;
 71             return true;
 72         }
 73     }
 74     return false;
 75 }
 76 void tarjan(int u,int fa,int del){
 77     dfn[u]=low[u]=++tmp;
 78     int flag=0;
 79     for (int i=lt[u];i;i=eg[i].nt){
 80         int v=eg[i].v;
 81         if (i/2==del) continue;
 82         if (v==fa && !flag){
 83             flag=1;
 84             continue;
 85         }
 86         if (!dfn[v]){
 87             tarjan(v,u,del);
 88             low[u]=min(low[u],low[v]);
 89             if (dfn[u]<low[v]) bridge[i/2]=1;
 90         }
 91         else low[u]=min(low[u],dfn[v]);
 92     }
 93 }
 94 
 95 int main(){
 96     scanf("%d %d",&n,&m);
 97     scanf("%d %d",&S,&T);
 98     sum=1;
 99     for (int i=1;i<=m;i++){
100         int u,v,w;
101         scanf("%d %d %d",&u,&v,&w);
102         add(u,v,w);
103     }
104 
105     clr(vis,0); 
106     clr(path,0);
107     if (!dfs(S)) { printf("0
0
"); return 0; }
108     else
109     {    
110         ans=INF;
111         for (int ii=1;ii<=path[0];ii++){
112             clr(bridge,0);
113             clr(vis,0);
114             clr(road,0);
115             clr(dfn,0);
116             tmp=0;             
117             for (int i=1;i<=n;i++)
118                 if (!dfn[i])
119                     tarjan(i,0,path[ii]);
120             if (!dfs_2(S,path[ii])){
121                 if (eg[path[ii]*2].w<ans){
122                     ans = eg[path[ii]*2].w;
123                     ANS[0]=1;
124                     ANS[1]=path[ii];
125                 }
126             }
127             else
128             {
129                 for (int i=1;i<=road[0];i++){
130                     if (bridge[road[i]]){
131                         if (eg[road[i]*2].w+eg[path[ii]*2].w<ans){
132                             ans=eg[road[i]*2].w+eg[path[ii]*2].w;
133                             ANS[0]=2;
134                             ANS[1]=road[i];
135                             ANS[2]=path[ii];
136                         }
137                     }
138                 }
139             }
140         }
141         if (ans==INF) printf("-1
");
142         else
143         {
144             printf("%d
%d
",ans,ANS[0]);
145             for (int i=1;i<=ANS[0];i++) printf("%d%c",ANS[i],i!=ANS[0]?' ':'
');
146         }
147     }    
148 }

View Code