HDU3251 最大流（最小割）

Being a Hero

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 30 Accepted Submission(s): 11

Problem Description

You are the hero who saved your country. As promised, the king will give you some cities of the country, and you can choose which ones to own!

But don't get too excited. The cities you take should NOT be reachable from the capital -- the king does not want to accidentally enter your area. In order to satisfy this condition, you have to destroy some roads. What's worse, you have to pay for that -- each road is associated with some positive cost. That is, your final income is the total value of the cities you take, minus the total cost of destroyed roads.

Note that each road is a unidirectional, i.e only one direction is available. Some cities are reserved for the king, so you cannot take any of them even if they're unreachable from the capital. The capital city is always the city number 1.

Input

The first line contains a single integer T (T <= 20), the number of test cases. Each case begins with three integers n, m, f (1 <= f < n <= 1000, 1 <= m < 100000), the number of cities, number of roads, and number of cities that you can take. Cities are numbered 1 to n. Each of the following m lines contains three integers u, v, w, denoting a road from city u to city v, with cost w. Each of the following f lines contains two integers u and w, denoting an available city u, with value w.

Output

For each test case, print the case number and the best final income in the first line. In the second line, print e, the number of roads you should destroy, followed by e integers, the IDs of the destroyed roads. Roads are numbered 1 to m in the same order they appear in the input. If there are more than one solution, any one will do.

Sample Input

Sample Output

Case 1: 3
1 4
Case 2: 4
2 1 3

Source

2009 Asia Regional Ningbo Online

题意：

有n个点，给出m条有向边以及边的权值，f个可以选择的点以及点的权值，需要割掉一些边（耗费边权值）得到一些点（得到点权值）使得得到的价值最大，问得到的最大价值以及割掉哪些边。

代码：

//可以取得f个点连向汇点，边权值为点权值，1为源点，把给出的边连接，建图，用总的点的权值减去
//最小割就是答案（如果有连向汇点的点，减法之后就相当于没有这条边没有这个点）。
//增广路算法结束时令已标号的节点(dc.vis[u]>0的节点)集合为S，其他节点集合为T=V-S。端点分别在
//两个集合中的边就是割边。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1009,inf=0x7fffffff;
int val[maxn],eu[100005],ev[100005],ew[100005];
struct edge{
    int from,to,cap,flow;
    edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct dinic{
    int n,m,s,t;
    vector<edge>edges;
    vector<int>g[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++) g[i].clear();
        edges.clear();
    }
    void addedge(int from,int to,int cap){
        edges.push_back(edge(from,to,cap,0));
        edges.push_back(edge(to,from,0,0));//反向弧
        m=edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }
    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int>q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=0;i<(int)g[x].size();i++){
                edge&e=edges[g[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t||a==0) return a;
        int flow=0,f;
        for(int&i=cur[x];i<(int)g[x].size();i++){
            edge&e=edges[g[x][i]];
            if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[g[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }
    int maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,inf);
        }
        return flow;
    }
}dc;
int main()
{
    int t,n,m,f,a,c,cas=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&f);
        dc.init(n+2);
        int s=1,t=n+1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&eu[i],&ev[i],&ew[i]);
            dc.addedge(eu[i],ev[i],ew[i]);
        }
        memset(val,0,sizeof(val));
        int sum=0;
        for(int i=1;i<=f;i++){
            scanf("%d%d",&a,&c);
            val[a]=c;
            sum+=c;
            dc.addedge(a,t,c);
        }
        int ans=dc.maxflow(s,t);
        printf("Case %d: %d
",++cas,sum-ans);
        int cnt=0,nu[100005];
        for(int i=1;i<=m;i++){
            if(dc.vis[eu[i]]>0&&dc.vis[ev[i]]==0&&ev[i]!=n+1)
            nu[++cnt]=i;
        }
        printf("%d",cnt);
        for(int i=1;i<=cnt;i++) printf(" %d",nu[i]);
        printf("
");
    }
    return 0;
}