首页 > ACM题库 > HDU-杭电 > HDU 3251-Being a Hero-网络流-[解题报告]HOJ
2014
03-13

HDU 3251-Being a Hero-网络流-[解题报告]HOJ

Being a Hero

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
4 4 2
1 2 2
1 3 3
3 2 4
2 4 1
2 3
4 4
4 4 2
1 2 2
1 3 3
3 2 1
2 4 1
2 3
4 4

样例输出:

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

/*
题意:给你f个可选城市,每个城市都有其价值w0,国王的城市在1,现在国王不想见到你(国王不想通过某种路径到达你选定的城市)——将你选的若干城市隔离出去,每条道路隔断都需要花费w1,现在问你可以达到的最大价值
并要求输出你割断的路的编号
题解:网络流模型题,将所有可选点连入超级汇点,求出最小割(等于最大流),最大价值为所有可选点的价值和减去最小割
我们默认最小割靠近源点的为左侧,靠近汇点为右侧
所有的割边的求法:最后一次求增广路的过程中,汇点不可达,此时从源点可增流的点都在记录路径的数组Qu里面
枚举数组里的值x,求出以x为起点,终点不在Qu中的所有边,这些边就是组成最小割的边
*/
#include <stdio.h>
#include <time.h>
#include <algorithm>
#include <map>
#include <string.h>
#include<queue>
#include<iostream>
#define N 60010
using namespace std;
const int maxn=1009;
const int inf=1<<30;
int n,m,f;
//**************************************************  
//为dinic求最大流模版  
struct edge  
{   
    int v, next;   
    int val;   
} net[ 200010 ];   
int Qnum;  //记录左侧点的数量
int level[maxn], Qu[maxn], out[maxn],next[maxn],ins[maxn],first[maxn];  
class Dinic {   
public:   
    int end;  
	int now;
	int low,high;
    Dinic() {   
        end = 0;   
        memset( next, -1, sizeof(next) );   
    }   
    inline void insert( int x, int y, int c) {   
        net[end].v = y, net[end].val = c,  
        net[end].next = next[x],   
        next[x] = end ++;   
        net[end].v = x, net[end].val = 0,  
        net[end].next = next[y],   
        next[y] = end ++;   
    }   
    bool BFS( int S, int E ) {   
        memset( level, -1, sizeof(level) );   
        low = 0, high = 1;   
        Qu[0] = S, level[S] = 0;   
        for( ; low < high; ) {   
            int x = Qu[low];   
            for( int i = next[x]; i != -1; i = net[i].next ) {   
                if( net[i].val == 0 ) continue;   
                int y = net[i].v;   
                if( level[y] == -1 ) {   
                    level[y] = level[x] + 1;   
                    Qu[ high ++] = y;   
                }   
            }   
            low ++;   
        }   
        return level[E] != -1;   
    }    
    
    int MaxFlow( int S, int E ){   
        int maxflow = 0;   
        for( ; BFS(S, E) ; ) {   
            memcpy( out, next, sizeof(out) );   
            now = -1;   
            for( ;; ) {   
                if( now < 0 ) {   
                    int cur = out[S];   
                    for(; cur != -1 ; cur = net[cur].next )    
                        if( net[cur].val && out[net[cur].v] != -1 && level[net[cur].v] == 1 )   
                            break;   
                    if( cur >= 0 ) Qu[ ++now ] = cur, out[S] = net[cur].next;   
                    else break;   
                }   
                int u = net[ Qu[now] ].v;   
                if( u == E ) {   
                    int flow = inf;   
                    int index = -1;   
                    for( int i = 0; i <= now; i ++ ) {   
                        if( flow > net[ Qu[i] ].val )   
                            flow = net[ Qu[i] ].val, index = i;   
                    }   
                    maxflow += flow;   
                    for( int i = 0; i <= now; i ++ )   
                        net[Qu[i]].val -= flow, net[Qu[i]^1].val += flow;   
                    for( int i = 0; i <= now; i ++ ) {   
                        if( net[ Qu[i] ].val == 0 ) {   
                            now = index - 1;   
                            break;   
                        }   
                    }   
                }   
                else{   
                    int cur = out[u];   
                    for(; cur != -1; cur = net[cur].next )    
                        if (net[cur].val && out[net[cur].v] != -1 && level[u] + 1 == level[net[cur].v])   
                            break;   
                    if( cur != -1 )   
                        Qu[++ now] = cur, out[u] = net[cur].next;   
                    else out[u] = -1, now --;   
                }   
            }   
        }   
		Qnum=high;//一定要记录此时在Qu数组里点的个数,方便后面枚举
        return maxflow;   
    }   
};   
  
struct E
{
	int v,next;
}edg[200011];
int ans;
void init(int k)
{
	int u,v,w;
	scanf("%d%d%d",&n,&m,&f);
	memset(ins,0,sizeof(ins));
	memset(first,-1,sizeof(first));
	Dinic my;
	int edg_num=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		edg[i].v=v;
		edg[i].next=first[u];
		first[u]=i;
		my.insert(u,v,w);
	}
	int sum=0;
	for(int i=0;i<f;i++)
	{
		scanf("%d%d",&u,&w);
		my.insert(u,n+1,w);
		sum+=w;
	}
	printf("Case %d: %d\n",k,sum-my.MaxFlow(1,n+1));
	sum=0;
	for(int i=0;i<Qnum;i++)
	ins[Qu[i]]=1;//标记所有左侧的点
	ans=0;
	//dfs(1);
	for(int i=0;i<Qnum;i++)
	{
		int x=Qu[i];
		for(int j=first[x];j!=-1;j=edg[j].next)
		{
			if(!ins[edg[j].v])
			out[ans++]=j;
		}
	}
	printf("%d",ans);
	for(int i=0;i<ans;i++)
	{
		printf(" %d",out[i]);
	}
	printf("\n");
}
int main() 
{
    int Case;
	scanf("%d",&Case);
	for(int i=1;i<=Case;i++)
	{
		init(i);
		//solve();
	}
    return 0;
}

参考:http://blog.csdn.net/wsniyufang/article/details/6719760


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. [email protected]