hdoj3251

这题告诉我们，最小割需：满流，S断不能到T端P4126,hdoj3987

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=,APB=,one=;

const lon INF=0x7FFFFFFF,mod=;

int n,m,cnt,sum,head[SSZ],dep[SSZ],snum;

int S=,T=,nex[SZ],to[SZ],wt[SZ];

int vst[SSZ];

struct nd{

    int x,y;

    nd(int a=,int b=):x(a),y(b){}

};

nd arr[SZ];

void add(int u,int v,int w)

{

    ++cnt;

    nex[cnt]=head[u];

    head[u]=cnt;

    to[cnt]=v,wt[cnt]=w;

}

void init()

{

    cnt=-,sum=;

    memset(head,-,sizeof(head));

    //cin>>n>>m>>snum;

    scanf("%d%d%d",&n,&m,&snum);

    for(int i=;i<=m;++i)

    {

        int a,b,c;

        //cin>>a>>b>>c;

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

        add(b,a,);

        arr[i].x=a,arr[i].y=b;

    }

    for(int i=;i<=snum;++i)

    {

        int id,val;

        cin>>id>>val;

        add(id,T,val);

        add(T,id,);

        sum+=val;

    }

    add(S,,INF);

    add(,S,);

}

bool bfs()

{

    memset(dep,,sizeof(dep));

    dep[S]=;

    queue<int> q;

    q.push(S);

    for(;q.size();)

    {

        int fr=q.front();

        q.pop();

        for(int i=head[fr];i!=-;i=nex[i])

        {

            int t=to[i],w=wt[i];

            if(!dep[t]&&w)

            {

                dep[t]=dep[fr]+;

                q.push(t);

                if(t==T)return ;

            }

        }

    }

    return ;

}

int dinic(int x,int flow)

{

    if(x==T)return flow;

    else

    {

        int rem=flow;

        for(int i=head[x];i!=-&&rem;i=nex[i])

        {

            int t=to[i],w=wt[i];

            if(dep[t]==dep[x]+&&w)

            {

                int tmp=dinic(t,min(rem,w));

                if(!tmp)dep[t]=;

                rem-=tmp;

                wt[i]-=tmp,wt[i^]+=tmp;

            }

        }

        return flow-rem;

    }

}

void dfs(int x,int p)

{

    //cout<<x<<endl;

    vst[x]=;

    for(int i=head[x];i!=-;i=nex[i])

    {

        int t=to[i],w=wt[i];

        if(t!=p&&w&&!vst[t])

        {

            dfs(t,x);

        }

    }

}

void work()

{

    int res=;

    for(;bfs();)res+=dinic(S,INF);

    cout<<sum-res<<endl;

    dfs(S,-);

    vector<int> tmp;

    for(int i=;i<=m;++i)

    {

        //cout<<arr[i].x<<" "<<arr[i].y<<endl;

        int u=arr[i].x,v=arr[i].y;

        if(vst[u]&&!vst[v])

        {

            tmp.push_back(i);

        }

    }

    cout<<tmp.size();

    for(int i=;i<tmp.size();++i)

    {

        printf(" %d",tmp[i]);

    }

    cout<<endl;

}

void release()

{

    memset(vst,,sizeof(vst));

}

int main()

{

    //std::ios::sync_with_stdio(0);

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    cin>>casenum;

    //cout<<casenum<<endl;

    for(int time=;time<=casenum;++time)

    //for(int time=1;cin>>n>>m;++time)

    {

        printf("Case %d: ",time);

        init();

        work();

        release();

    }

    return ;

}