首页 > ACM题库 > HDU-杭电 > hdu 2480 Steal the Treasure-贪心-[解题报告]C++
2014
01-26

hdu 2480 Steal the Treasure-贪心-[解题报告]C++

Steal the Treasure

问题描述 :

The alliance of thieves decides to steal the treasure from country A. There are n cities in country A. Cities are connected by directional or bidirectional road. To avoid the risk, the king of country A divides his treasure and hides them in some place on the road.
  The alliance has found out the secret of the king. They get a map of country A which shows the location and the quantity of treasure on each road. In order to make the maximum profit and reduce the least loss, the alliance determines to send n thieves respectively to each city (one city one thief). At the appointed time, each thief chooses one road (if there is a road and notice that the road may have direction) to get to its corresponding city. Then he can steal the treasure on that road. After stealing, all the thieves return back to their base immediately.
  The heads of the alliance wonder to know the quantity of the treasure they can steal at most.

输入:

There are multiple cases. Input is terminated by EOF.
  For each case, the first line contains two integers n (1<=n<=1000) and m (0<=m<=n*(n-1)/2), representing the number of cities and the number of roads in country A. The following m lines, each line contains four integers x, y (1<=x, y<=n, x≠y), d (0<=d<=1), w (0<=w<=1000), which means that there is a road from city x to city y, d=0 shows this road is bidirectional and d=1 shows it is directional and x the starting point, w is the quantity of treasure on the road.
  We guarantee that the road (x, y) and (y, x) will never appear together in the same case.

输出:

There are multiple cases. Input is terminated by EOF.
  For each case, the first line contains two integers n (1<=n<=1000) and m (0<=m<=n*(n-1)/2), representing the number of cities and the number of roads in country A. The following m lines, each line contains four integers x, y (1<=x, y<=n, x≠y), d (0<=d<=1), w (0<=w<=1000), which means that there is a road from city x to city y, d=0 shows this road is bidirectional and d=1 shows it is directional and x the starting point, w is the quantity of treasure on the road.
  We guarantee that the road (x, y) and (y, x) will never appear together in the same case.

样例输入:

2 1
1 2 0 10
5 5
1 2 1 0
1 3 1 10
2 3 0 20
3 4 0 30
4 2 1 40

样例输出:

10
100

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1000 + 5;
const int INF = 1000000000;

struct Edge{
    int from,to,d,w;
}e[maxn*maxn];

bool cmp(Edge a,Edge b){
    return a.w < b.w;
}

int vis[maxn];
int fa[maxn];

int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        for(int i = 0;i < m;i++){
            scanf("%d%d%d%d",&e[i].from,&e[i].to,&e[i].d,&e[i].w);
        }
        sort(e,e+m,cmp);
        memset(vis,0,sizeof(vis));
        for(int i = 0;i <= n;i++) fa[i] = i;
        int ans = 0;
        for(int i = m-1;i >= 0;i--){
            int x = Find(e[i].from);
            int y = Find(e[i].to);
            if(vis[x] && vis[y]) continue;
            else if(e[i].d == 1 && vis[x]) continue;
            ans += e[i].w;
            if(e[i].d == 1) vis[x] = 1;
            else{
                if(x == y) vis[x] = 1;
                if(vis[x] == 0 && vis[y] == 0 ) fa[x] = y;
                else if(vis[x] == 1) vis[y] = 1;
                else if(vis[y] == 1) vis[x] = 1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/wiking__acm/article/details/12563785


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])