HDU 6187 Destroy Walls(対偶図最小生成ツリー)
Destroy Walls
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 236 Accepted Submission(s): 96
Problem Description 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√).
There are n towers in the city, which numbered from 1 to n. The ith’s location is (xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower ui and the tower vi(including the endpoint). The cost of destroying the ith wall is 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.
Then m lines follow, the ith line contains 3 integers ui,vi,wi
|xi|,|yi|≤105
3≤n≤100000,1≤m≤200000
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
Source 2017 A CM/ICCC広西招待試合-再現試合(広西大学に感謝)
Recommend liuyiding
テーマ:
V個のノードM個の辺の帯辺権無方向平面図があり、ある人は1つの領域にいて、いくつかの壁を分解して彼が任意の領域に着くことができて、最小費用を聞く.
問題解決の考え方:
まず,問題は平面図対偶図の最小生成ツリーを要求することであることが分かった.Euler式によれば,k個の連通成分を持つ平面図に対する領域数r=E−V+k+1を知ることができる.では、対偶図生成ツリーの辺数はr−1=E−V+kであり、これらの辺は削除する原図の辺であり、残りの辺数はV−kであり、これが原図の連通成分毎に生成されるツリーの辺数の和である.原図の各連通成分を保持する生成ツリーを考慮すると,明らかに要求を満たす.問題は費用が最小であることを要求して、つまり残した辺の重みの値が最大で、それでは私達は直接各連通成分に対して最大の生成木を求めることができて、削除する辺の数は総辺の数から生成木の辺の数とを差し引いて、最小の費用はすべての辺の費用から最大の生成木の費用を差し引くことです.
ACコード:
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 236 Accepted Submission(s): 96
Problem Description 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√).
There are n towers in the city, which numbered from 1 to n. The ith’s location is (xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower ui and the tower vi(including the endpoint). The cost of destroying the ith wall is 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.
Then m lines follow, the ith line contains 3 integers ui,vi,wi
|xi|,|yi|≤105
3≤n≤100000,1≤m≤200000
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
Source 2017 A CM/ICCC広西招待試合-再現試合(広西大学に感謝)
Recommend liuyiding
テーマ:
V個のノードM個の辺の帯辺権無方向平面図があり、ある人は1つの領域にいて、いくつかの壁を分解して彼が任意の領域に着くことができて、最小費用を聞く.
問題解決の考え方:
まず,問題は平面図対偶図の最小生成ツリーを要求することであることが分かった.Euler式によれば,k個の連通成分を持つ平面図に対する領域数r=E−V+k+1を知ることができる.では、対偶図生成ツリーの辺数はr−1=E−V+kであり、これらの辺は削除する原図の辺であり、残りの辺数はV−kであり、これが原図の連通成分毎に生成されるツリーの辺数の和である.原図の各連通成分を保持する生成ツリーを考慮すると,明らかに要求を満たす.問題は費用が最小であることを要求して、つまり残した辺の重みの値が最大で、それでは私達は直接各連通成分に対して最大の生成木を求めることができて、削除する辺の数は総辺の数から生成木の辺の数とを差し引いて、最小の費用はすべての辺の費用から最大の生成木の費用を差し引くことです.
ACコード:
#include int x, y;
scanf("%d%d", &x, &y);
}
LL ans=0;
for(int i=0;iscanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
ans+=edge[i].cost;
}
sort(edge, edge+E);
int cnt=0;//
for(int i=0;iif(unite(edge[i].from, edge[i].to))
{
ans-=edge[i].cost;
++cnt;
}
printf("%d %lld
", E-cnt, ans);
}
return 0;
}