UVA - 10480(最小割路径)

UVA - 10480

题意：

给你一个网络图，开始时候有 $n$ ， $m$ 两个整数，分别代表顶点个数和边的个数。下面 $m$ 行，每个边有三个整数 $u, v, w$ 组成，代表 $u$ 到 $v$ 有一条无向边，费用为 $w$ 。

现在让你把图破坏某些边，分成两个部分即与 $1$ 连接部分的和与 $2$ 连接部分，现在让你求破坏费用最小的的的情况下，需要破坏那些边。

分析：

最大流最小割定理， $s$ 到 $t$ 的最小割的边就是 $s$ 到 $t$ 的最大流的上的关键边.

接下来怎么求残余网络的关键边？

跑一边最大流之后， 让可以与源点 $s $ 联通的顶点标记，接下来遍历所有边，如果该边的一个顶点标记，而另一个顶点未标记，那么这就是其中一个关键边。

代码:

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=70;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
struct edge
{
    int to,flow,cap,rev;//rev 代表反向边在 to的第几个边
    edge() {}
    edge(int to,int cap, int rev,int flow=0)
    {
        this->to=to,this->cap=cap,this->rev=rev;
        this->flow=flow;
    }
};
bool book[maxn];
class EK
{
public:
    vector<edge> adja[maxn];
    int prevv[maxn],preve[maxn];
    int top;
    void init(int n) //编号从1开始
    {
        for(int i=0; i<=n; ++i) adja[i].clear();
        top=n;
    }
    void addEdge(int u,int v,int cap)
    {
        adja[u].push_back(edge(v,cap,adja[v].size()));
        adja[v].push_back(edge(u,0,adja[u].size()-1));
    }
    void bfs(int s,int t)
    {
        queue<int> mmp;
        mset(prevv,-1);
        mmp.push(s),prevv[s]=s;
        while(!mmp.empty())
        {
            int u=mmp.front();
            mmp.pop();
            if(u==t) return  ;
            for(int i=0; i<adja[u].size(); ++i)
            {
                edge &e=adja[u][i];
                if(e.cap-e.flow>0&&prevv[e.to]==-1)
                {
                    prevv[e.to]=u;
                    preve[e.to]=i;
                    mmp.push(e.to);
                }
            }
        }

    }
    int maxFlow(int s,int t)
    {
        int flow=0;
        for(;;)
        {
            bfs(s,t);
            if(prevv[t]==-1)
                return flow;
            int minn=inf;
            for(int v=t; v!=prevv[v]; v=prevv[v])
            {
                edge& e=adja[prevv[v]][preve[v]];
                minn=min(minn,e.cap-e.flow);
            }
            for(int v=t; v!=prevv[v]; v=prevv[v])
            {
                edge& e=adja[prevv[v]][preve[v]];
                e.flow+=minn;
                adja[v][e.rev].flow-=minn;
            }
            flow+=minn;
        }
    }
    void solve(){//遍历源点可以到达的边
        mset(book,false);
        queue<int> mmp;
        mmp.push(1);book[1]=true;
        while(!mmp.empty()){
            int u=mmp.front();
            mmp.pop();
            for(int i=0;i<adja[u].size();++i){
                edge &e=adja[u][i];
                if(e.cap>e.flow&& !book[e.to]){
                    book[e.to]=true;
                    mmp.push(e.to);
                }
        }
    }
    }
};
/* 染色 */
EK kit;
bool isPrint[maxn][maxn];
int  main()
{
    int n,m,u,v,w,cap;
    while(scanf("%d%d",&n,&m),n)
    {
        kit.init(n);
        for(int i=0; i<m; ++i)
        {
            scanf("%d%d%d",&u,&v,&cap);
            kit.addEdge(u,v,cap);
            kit.addEdge(v,u,cap);
        }
        kit.maxFlow(1,2);
        kit.solve();
        mset(isPrint,false);
        for(int u=1;u<=n;++u){
            for(edge &e:kit.adja[u]){
                if(book[u]!=book[e.to]&&isPrint[u][e.to]==false){
                    printf("%d %d\n",u,e.to);
                    isPrint[u][e.to]=isPrint[e.to][u]=true;
                }
            }
        }
        puts("");
    }
    return 0;
}