n<=1000，m<=30000的图，问割掉边权和尽量小的0、1或2条边使S和T不连通，输出割了哪些边，无解-1.
道理是很好懂的，先随便找S到T的一条路径，找不到输出0，找到的话这条路上至少有一条边要删，那枚举一下割谁，对剩下的图再做tarjan即可。复杂度(n*m)。
然而！！写起来是很难写的。。
方法一：一开始把所有S到T的路径上的边都标记好，枚举割的第一条边后跑完tarjan，直接看这些边会不会是割边再取min即可。
方法二：枚举割的第一条边后，tarjan求个边双，然后缩起来建树，在树上搜一次。
方法二。
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 #include<vector> 5 //#include<assert.h> 6 #include<algorithm> 7 //#include<iostream> 8 using namespace std; 9 10 int n,m,s,t; 11 #define maxn 1011 12 #define maxm 60011 13 struct Edge{int to,v,next;}edge[maxm]; int first[maxn],le=2; 14 void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;} 15 void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);} 16 17 int list[maxn],ll=0,ans,numofans,whoisans[5]; 18 bool vis[maxn]; 19 bool dfs(int x) 20 { 21 if (x==t) return 1; 22 vis[x]=1; 23 for (int i=first[x];i;i=edge[i].next) 24 { 25 const Edge &e=edge[i]; if (vis[e.to]) continue; 26 list[++ll]=i>>1; 27 if (dfs(e.to)) return 1; 28 ll--; 29 } 30 return 0; 31 } 32 33 int bel[maxn],tot,Time,low[maxn],dfn[maxn],sta[maxn],top; 34 struct Tree 35 { 36 struct Edge{int to,v,id,next;}edge[maxm]; int first[maxn],le; 37 void in(int x,int y,int v,int id) {Edge &e=edge[le];e.to=y;e.v=v;e.id=id;e.next=first[x];first[x]=le++;} 38 void insert(int x,int y,int v,int id) {in(x,y,v,id); in(y,x,v,id);} 39 bool vis[maxn],ok; int select,selectv; 40 void clear() 41 { 42 memset(vis,0,sizeof(vis)); ok=0; 43 memset(first,0,sizeof(first)); le=2; 44 } 45 void dfs(int x,int fa,int Min,int Minid) 46 { 47 if (ok) return; 48 if (x==bel[t]) 49 { 50 ok=1; 51 if (selectv+Min<ans) 52 { 53 ans=selectv+Min; 54 numofans=2; 55 whoisans[1]=select; whoisans[2]=Minid; 56 } 57 return; 58 } 59 vis[x]=1; 60 for (int i=first[x];i && !ok;i=edge[i].next) 61 { 62 const Edge &e=edge[i]; if (vis[e.to]) continue; 63 dfs(e.to,x,min(Min,e.v),e.v<Min?e.id:Minid); 64 } 65 } 66 }T; 67 68 void tarjan(int x,int f,int who) 69 { 70 low[x]=dfn[x]=++Time; sta[++top]=x; vis[x]=1; 71 for (int i=first[x];i;i=edge[i].next) 72 { 73 if (i==f || i==(f^1) || i==(who<<1) || i==((who<<1)^1)) continue; 74 const Edge &e=edge[i]; 75 if (!dfn[e.to]) tarjan(e.to,i,who),low[x]=min(low[x],low[e.to]); 76 else if (vis[e.to]) low[x]=min(low[x],dfn[e.to]); 77 } 78 if (low[x]==dfn[x]) 79 { 80 tot++; 81 while (sta[top]!=x) bel[sta[top]]=tot,vis[sta[top--]]=0; 82 bel[sta[top--]]=tot,vis[x]=0; 83 } 84 } 85 86 void tarjan(int select) 87 { 88 top=tot=Time=0; 89 memset(dfn,0,sizeof(dfn)); 90 memset(vis,0,sizeof(vis)); 91 for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0,select); 92 if (bel[s]==bel[t]) return; 93 T.clear(); 94 for (int i=1;i<=n;i++) 95 for (int j=first[i];j;j=edge[j].next) if ((j>>1)!=select) 96 { 97 const Edge &e=edge[j]; 98 if (bel[i]!=bel[e.to]) T.in(bel[i],bel[e.to],e.v,j>>1); 99 } 100 T.select=select; T.selectv=edge[select<<1].v; 101 T.dfs(bel[s],0,0x7fffffff,0); 102 if (!T.ok) {if (edge[select<<1].v<ans) {ans=edge[select<<1].v; numofans=1; whoisans[1]=select;}} 103 } 104 105 int main() 106 { 107 scanf("%d%d%d%d",&n,&m,&s,&t); 108 for (int i=1,x,y,v;i<=m;i++) scanf("%d%d%d",&x,&y,&v),insert(x,y,v); 109 dfs(s); 110 if (ll==0) {puts("0 0"); return 0;} 111 numofans=-1; ans=0x7fffffff; 112 for (int i=1;i<=ll;i++) tarjan(list[i]); 113 if (numofans==-1) puts("-1"); 114 else 115 { 116 printf("%d %d ",ans,numofans); 117 for (int i=1;i<=numofans;i++) printf("%d ",whoisans[i]); 118 } 119 return 0; 120 }