题目传送门: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; }
I’d have to examine with you here. Which is not one thing I usually do! I take pleasure in reading a post that may make folks think. Additionally, thanks for permitting me to comment!
you have a great blog here! would you like to make some invite posts on my blog?