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）。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 100008
#define V 1008
#define E 60008
#define lson l,m,rt<<1
#define rson m,r+1,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define LL long long const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/ int n,m,S,T,tmp;
int vis[V],path[V],dfn[V],low[V],road[V],bridge[E];
int ans;
int ANS[V];
struct line{
int u,v,w,nt;
}eg[E];
int sum,lt[V]; void adt(int u,int v,int w){
eg[++sum]=(line){u,v,w,lt[u]};
lt[u]=sum;
}
void add(int u,int v,int w){
adt(u,v,w); adt(v,u,w);
} bool dfs(int u){
vis[u]=;
if (u==T) return true;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (vis[v]) continue;
if (dfs(v)){
path[++path[]]=i/;
return true;
}
}
return false;
} bool dfs_2(int u,int del){
vis[u]=;
if (u==T) return true;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (i/==del) continue;
if (vis[v]) continue;
if (dfs_2(v,del)){
road[++road[]]=i/;
return true;
}
}
return false;
}
void tarjan(int u,int fa,int del){
dfn[u]=low[u]=++tmp;
int flag=;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (i/==del) continue;
if (v==fa && !flag){
flag=;
continue;
}
if (!dfn[v]){
tarjan(v,u,del);
low[u]=min(low[u],low[v]);
if (dfn[u]<low[v]) bridge[i/]=;
}
else low[u]=min(low[u],dfn[v]);
}
} int main(){
scanf("%d %d",&n,&m);
scanf("%d %d",&S,&T);
sum=;
for (int i=;i<=m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
} clr(vis,);
clr(path,);
if (!dfs(S)) { printf("0\n0\n"); return ; }
else
{
ans=INF;
for (int ii=;ii<=path[];ii++){
clr(bridge,);
clr(vis,);
clr(road,);
clr(dfn,);
tmp=;
for (int i=;i<=n;i++)
if (!dfn[i])
tarjan(i,,path[ii]);
if (!dfs_2(S,path[ii])){
if (eg[path[ii]*].w<ans){
ans = eg[path[ii]*].w;
ANS[]=;
ANS[]=path[ii];
}
}
else
{
for (int i=;i<=road[];i++){
if (bridge[road[i]]){
if (eg[road[i]*].w+eg[path[ii]*].w<ans){
ans=eg[road[i]*].w+eg[path[ii]*].w;
ANS[]=;
ANS[]=road[i];
ANS[]=path[ii];
}
}
}
}
}
if (ans==INF) printf("-1\n");
else
{
printf("%d\n%d\n",ans,ANS[]);
for (int i=;i<=ANS[];i++) printf("%d%c",ANS[i],i!=ANS[]?' ':'\n');
}
}
}