学步园

题意：给n（1<=n<=1000）个点m（0<=m<=n*(n-1) / 2）条边每条边有一定的财宝，但是每条边的方向不固定（双向或者单向），现在每个点上有一个小

         偷，想使得所有小偷得到的钱最多（小偷要沿着边的方向走并且只能走到相邻的一条边），问最多能得到多少财宝。

题解：想法贪心，把所有边按照边权从大到小排序，对于单向边如果当前起始点的小偷还可以偷，那么就偷这条边，那么双向边如何处理呢？想象一个由x个点

          x-1条双向边组成的连通块，如果此时规定一个点指出去的方向那么其他点的方向就能定下来，并查集维护双向边的集合。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 1002;
const int maxm = 500002;
struct node
{
    int u,v,w,d;
    bool operator < (const node &other) const
    {
        return w > other.w;
    }
}edge[maxm];
int father[maxn];
bool vis[maxn];
int m,n;

int find(int u)
{
    return (u == father[u]) ? father[u] : (father[u] = find(father[u]));
}

void read()
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) father[i] = i;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d %d",&edge[i].u,&edge[i].v,&edge[i].d,&edge[i].w);
    }
    sort(edge , edge + m);
    return;
}

void solve()
{
    int sum = 0;
    for(int i=0;i<m;i++)
    {
        int x = find(edge[i].u);
        int y = find(edge[i].v);
        if(vis[x] && vis[y]) continue;
        if(edge[i].d == 1 && vis[x]) continue;
        sum += edge[i].w;
        if(edge[i].d == 1) vis[x] = true;
        else
        {
            if(x == y) vis[x] = true;
            else if(vis[x]) vis[y] = true;
            else if(vis[y]) vis[x] = true;
            else father[y] = x;
        }
    }
    printf("%d\n",sum);
    return;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        read();
        solve();
    }
    return 0;
}