hdoj3251

佚名 5年前 (2019-04-25) 随笔 1301人围观抢沙发百度已收录

这题告诉我们，最小割需：满流，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-12;
typedef long long lon;
const lon SZ=500010,SSZ=1010,APB=26,one=1;
const lon INF=0x7FFFFFFF,mod=1000000007;
int n,m,cnt,sum,head[SSZ],dep[SSZ],snum;
int S=1007,T=1008,nex[SZ],to[SZ],wt[SZ];
int vst[SSZ];
struct nd{
    int x,y;
    nd(int a=0,int b=0):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=-1,sum=0;
    memset(head,-1,sizeof(head));
    //cin>>n>>m>>snum;
    scanf("%d%d%d",&n,&m,&snum);
    for(int i=1;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,0);
        arr[i].x=a,arr[i].y=b;
    }
    for(int i=1;i<=snum;++i)
    {
        int id,val;
        cin>>id>>val;
        add(id,T,val);
        add(T,id,0);
        sum+=val;
    }
    add(S,1,INF);
    add(1,S,0);
}

bool bfs()
{
    memset(dep,0,sizeof(dep));
    dep[S]=1;
    queue<int> q;
    q.push(S);
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        for(int i=head[fr];i!=-1;i=nex[i])
        {
            int t=to[i],w=wt[i];
            if(!dep[t]&&w)
            {
                dep[t]=dep[fr]+1;
                q.push(t);
                if(t==T)return 1;
            }
        }
    }
    return 0;
}

int dinic(int x,int flow)
{
    if(x==T)return flow;
    else
    {
        int rem=flow;
        for(int i=head[x];i!=-1&&rem;i=nex[i])
        {
            int t=to[i],w=wt[i];
            if(dep[t]==dep[x]+1&&w)
            {
                int tmp=dinic(t,min(rem,w));
                if(!tmp)dep[t]=0;
                rem-=tmp;
                wt[i]-=tmp,wt[i^1]+=tmp;
            }
        }
        return flow-rem;
    }
}

void dfs(int x,int p)
{
    //cout<<x<<endl;
    vst[x]=1;
    for(int i=head[x];i!=-1;i=nex[i])
    {
        int t=to[i],w=wt[i];
        if(t!=p&&w&&!vst[t])
        {
            dfs(t,x);
        }
    }
}

void work()
{
    int res=0;
    for(;bfs();)res+=dinic(S,INF);
    cout<<sum-res<<endl;
    dfs(S,-1);
    vector<int> tmp;
    for(int i=1;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=0;i<tmp.size();++i)
    {
        printf(" %d",tmp[i]);
    }
    cout<<endl;
}

void release()
{
    memset(vst,0,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=1;time<=casenum;++time)
    //for(int time=1;cin>>n>>m;++time)
    {
        printf("Case %d: ",time);
        init();
        work();
        release();
    }
    return 0;
}