根据最大流最小割定理,最大流的值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
小阮 阅读(836)
评论(0) 编辑 收藏 引用 所属分类:
USACO