【Codeforces 700C】Break Up

题目传送门：http://codeforces.com/problemset/problem/700/C
官方题解：http://codeforces.com/blog/entry/46283

最开始，瞄一眼：“这™不狼抓兔子吗？”
于是死坑在网络流上
发现，网络流只能保证总费用最小，但实在是保证不了边数最小
比如这个图：
于是还是按照官方给的题解，码的求割顶的代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;
const int M = 60000+9;
const int INF = 0x7fffffff;

int n,m,s,t,vout=INF,vis[N],tag[M],tot,sign,upd;
int head[N],nxt[M],to[M],val[M],link[N],num[N];
 queue<int> que,path,ans;

inline void AddEdge(int a, int b, int w){
	static int T = 1;
	to[++T] = b; nxt[T] = head[a]; head[a] = T; val[T] = w;
	to[++T] = a; nxt[T] = head[b]; head[b] = T; val[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

bool DFS(int w){
	if (w == t) return 1; else vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (!vis[to[i]]) 
		if (DFS(to[i])) {path.push(i); return 1;}
	return 0;
}

int Get_Cut(int w, int f){
	if (!num[w]) link[w] = num[w] = ++tot; int ret = w==t?1:0;
	for (int i=head[w];i;i=nxt[i]) if (!tag[i] && (i^1) != f) {
		if (num[to[i]]) link[w] = min(link[w],num[to[i]]);
		else {
			int tmp = Get_Cut(to[i],i);
			if (link[to[i]] > num[w]) {if (tmp && (upd==INF || val[upd] > val[i])) upd = i;} 
			else link[w] = min(link[w], link[to[i]]);
			ret |= tmp;
		}
	}
	return ret;
}

inline bool BFS(){
	memset(vis,0,sizeof(vis));
	que.push(s); vis[s] = 1;
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (!tag[i]) 
			if (!vis[to[i]]) vis[to[i]] = 1, que.push(to[i]);
	} 
	return vis[t];
}

inline void update(int a, int b){
	if (vout > val[a] + val[b]) {
		vout = val[a] + val[b];
		while (!ans.empty()) ans.pop(); 
		ans.push(a); if (b) ans.push(b);
	}
}

int main(){
	n = read(); m = read(); s = read(); t = read();
	for (int i=1,u,v,w;i<=m;i++) u=read(), v=read(), w=read(), AddEdge(u,v,w);
	if (DFS(s)) {
		while (!path.empty()) {
			int w = path.front(); 
			tag[w] = tag[w^1] = 1;
			if (BFS()) {
				memset(link,0,sizeof(link)); 
				memset(num,0,sizeof(num)); upd = INF;
				link[s] = num[s] = tot = 1; Get_Cut(s,-1);
				if (upd != INF) update(upd,w);
			} else update(w,0);
			tag[w] = tag[w^1] = 0; path.pop();
		}
		if (vout == INF) cout<<-1;
		else {
			cout<<vout<<endl<<ans.size()<<endl;
			while (!ans.empty()) cout<<ans.front()/2<<' ', ans.pop();
		}
	} else cout<<0<<endl<<0;	
	return 0;
}