随笔-141  评论-9  文章-3  trackbacks-0
根据最大流最小割定理,最大流的值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, 
sizeoflong)*MAXN*MAXN);
}


long pre[MAXN], delta[MAXN];

bool bfs(int s, int t){

    queue
<int> Q;

    memset(pre, 
0sizeof(pre));
    memset(delta, 
0sizeof(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, 
sizeoflong)*MAXN*MAXN);

        c[edges[i].s][edges[i].t] 
-= edges[i].cost;

        
long maxt = edmonds_karp(1, n);

        
if(maxt+== 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 小阮 阅读(821) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理