根据最大流最小割定理，最大流的值flow就等于最小割的流量。
求最小割的边集：枚举每条边，该边的值为t， 从图中去掉这条边，然后求最大流maxt。
如果 maxt + t = flow 则这条边属于最小割的边集，flow -= t 。继续枚举。
另外，为了构造解，我记录了输入的顺序并对边的大小和答案进行了排序。 我看到有些牛人的题解不需要排序，学习中。
/**//*
ID: lorelei3
TASK: milk6
LANG: C++
*/
#include <fstream>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAXM = 1005;
const int MAXN = 33;
const int INF = 0x7FFFFFFF;
ifstream fin("milk6.in");
ofstream fout("milk6.out");
struct Edge
{
int index, s, t;
long cost ;
bool operator < ( const Edge &e)const {
return (cost>e.cost) || (cost==e.cost && index<e.index );
}
};
int n,m;
int cnt;
Edge edges[MAXM];
long c[MAXN][MAXN];
long tmp[MAXN][MAXN];
void input(){
fin>>n>>m;
for(int i=1; i<=m; ++i){
edges[i].index=i;
fin>>edges[i].s>>edges[i].t>>edges[i].cost;
c[edges[i].s][edges[i].t] += edges[i].cost;
}
memcpy(tmp, c, sizeof( long)*MAXN*MAXN);
}
long pre[MAXN], delta[MAXN];
bool bfs(int s, int t){
queue<int> Q;
memset(pre, 0, sizeof(pre));
memset(delta, 0, sizeof(delta));
delta[s]=INF;
Q.push(s);
while(!Q.empty()){
int cur = Q.front();
Q.pop();
for(int i=1; i<=n; ++i){
if(delta[i]==0 && c[cur][i]>0 ){
delta[i] = delta[cur]<c[cur][i] ? delta[cur] : c[cur][i];
pre[i] = cur;
Q.push(i);
}
}
}
if(delta[t]==0)
return false;
return true;
}
long edmonds_karp(int s, int t){
long ans=0;
while(bfs(s,t)){
for(int i=t; i!=s; i=pre[i]){
c[pre[i]][i] -= delta[t];
c[i][pre[i]] += delta[t];
}
ans += delta[t];
}
return ans;
}
int tot;
int ans[MAXM];
long maxflow, flow;
void solve(){
sort(edges+1, edges+m+1);
flow = edmonds_karp(1, n);
maxflow = flow;
for(int i=1; i<=m; ++i){
long t = edges[i].cost;
memcpy(c, tmp, sizeof( long)*MAXN*MAXN);
c[edges[i].s][edges[i].t] -= edges[i].cost;
long maxt = edmonds_karp(1, n);
if(maxt+t == flow){
ans[tot++] = edges[i].index;
flow -= edges[i].cost;
tmp[edges[i].s][edges[i].t] -= edges[i].cost;
}
}
}
void output(){
fout<<maxflow<<" "<<tot<<endl;
sort(ans, ans+tot);
for(int i=0; i<tot; ++i)
fout<<ans[i]<<endl;
}
int main(){
input();
solve();
output();
return 0;
}
posted on 2011-02-02 13:57
小阮 阅读(819)
评论(0) 编辑 收藏 引用 所属分类:
USACO