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