HDU 6187 Destroy Walls（最大生成树）

蔚落 2022-06-09 12:19 128阅读 0赞

Long times ago, there are beautiful historic walls in the city. These walls divide the city into many parts of area.  
  
Since it was not convenient, the new king wants to destroy some of these walls, so he can arrive anywhere from his castle. We assume that his castle locates at (0.6∗2–√,0.6∗3–√) (0.6∗2,0.6∗3).  
  
There are n n towers in the city, which numbered from 1 to n. The ith's location is (xi,yi) (xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower ui ui and the tower vi vi(including the endpoint). The cost of destroying the ith wall is wi wi.  
  
Now the king asks you to help him to divide the city. Firstly, the king wants to destroy as less walls as possible, and in addition, he wants to make the cost least.  
  
The walls only intersect at the endpoint. It is guaranteed that no walls connects the same tower and no 2 walls connects the same pair of towers. Thait is to say, the given graph formed by the walls and towers doesn't contain any multiple edges or self-loops.  
  
Initially, you should tell the king how many walls he should destroy at least to achieve his goal, and the minimal cost under this condition.

Input

There are several test cases.  
  
For each test case:  
  
The first line contains 2 integer n, m.  
  
Then next n lines describe the coordinates of the points.  
  
Each line contains 2 integers xi,yi xi,yi.  
  
Then m lines follow, the ith line contains 3 integers ui,vi,wi ui,vi,wi  
  
|xi|,|yi|≤105 |xi|,|yi|≤105  
  
3≤n≤100000,1≤m≤200000 3≤n≤100000,1≤m≤200000  
  
1≤ui,vi≤n,ui≠vi,0≤wi≤10000 1≤ui,vi≤n,ui≠vi,0≤wi≤10000

Output

For each test case outout one line with 2 integers sperate by a space, indicate how many walls the king should destroy at least to achieve his goal, and the minimal cost under this condition.

Sample Input

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

Sample Output

1 1

题解：

让你求一颗最大生成树，输出点数n-选入生成树中的点数ans和边的值总和-生成树的值。。。前面输入点的坐标是废话，注意一开始wa了一次是因为还以为一定可以形成生成树第一个输出写成了m-n+1就错了，改成n-ans就对了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-7
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    const int maxn=2e5+5;
    int pre[100005];
    struct node
    {
        int f,t;
        int v;
    }a[maxn];
    int cmp(node x,node y)
    {
        return x.v>y.v;
    }
    int find(int x)
    {
        if(x!=pre[x])
            pre[x]=find(pre[x]);
        return pre[x];
    }
    int main()
    {
        int i,j,k,x,y,z,n,m,ans,d1,d2;
        ll sum,s;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            s=0;
            for(i=1;i<=n;i++)
            {
                scanf("%d%d",&x,&y);
                pre[i]=i;
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&a[i].f,&a[i].t,&a[i].v);
                s+=a[i].v;
            }
            sort(a,a+m,cmp);
            sum=0;
            ans=0;
            for(i=0;i<m;i++)
            {
                d1=find(a[i].f);
                d2=find(a[i].t);
                if(d1!=d2)
                {
                    pre[d2]=d1;
                    ans++;
                    sum+=a[i].v;
                    if(ans>=n-1)
                        break;
                }
            }
            printf("%d %lld\n",m-ans,s-sum);
        }
        return 0;
    }