1001. Battle Over Cities - Hard Version (35)

It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.

Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<=500), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers:

City1 City2 Cost Status

where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.

Note: It is guaranteed that the whole country was connected before the war.

Output Specification:

For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.

In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.

Sample Input 1:

4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 1 0

Sample Output 1:

1 2

Sample Input 2:

4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1

Sample Output 2:

0

   以上就是浙大PAT（Programming Ability Test)上的一道题。首先理解理解本题题意，城市之间本来是通过轨道两两连通的，当某一个城市被占领后，从该城市连通出去的轨道必须毁掉，而剩下的城市之间通过修复已经废弃的轨道来重新建立保持彼此连通，轨道越长，修复代价越大，那么该城市的重要性越大。题目输出所有重要性最大的城市，可能不止一个，也可能为零个。

   其实，个人理解，本题的主要考察图的连通性问题，涉及到其中两个方面，1）如何判断两个点是否连通（两个城市是否连通），2）如何将两个连通子图合并（选择修复那条轨道来保证两个城市簇连通）。对于以上问题，可以如下考虑：

   对于一个连通图，额外添加一个指针，使得该图的每一个节点的指针指向该图的某一个节点，实现可以为root[i]=s；其中i是连通图中的每一个节点，s为连通图的某一个节点,称之为根节点，为了使得s突出，root[s]=-1;那么，j所在的连通图和k所在的连通图是否是连通就看root[j]==root[k]是否成立了，更进一步，当将j所在的连通图和k所在的连通图合并时，我们只需要将root[j]赋值给root[k]即可。则，一个连通图求解其s的过程可以如下：1）初始条件，每一个点都是一个连通图。2）每读入一条边，然后将两个节点所在的连通图合并。具体实现过程如下：

int findroot(int id)
{
if(root[id]==-1)//本节点就是根节点
return id;
int x=findroot(root[id]);/*本语句的原因，两个连通图S1(根节点r1)、S2(根节点r2)合并，

只是将r2的根节点设为r1，所以当S1，S2合并后，S2中的节点的根节点并未修改，当求S2中节点的根节点时，需要先找到r2,再通过r2找到r1*/

root[id]=x;//及时修改以上情况下S2中节点的根节点为人r1
return x;
}

   这样，当某个城市被占领后，我们将剩下的城市划分成几个连通子图（即有几个root[i]==-1,根节点为-1)，然后从废弃的轨道集合中从小到大依次选择轨道两端城市分别在两个连通子图上的边，修复该边，合并这两个连通子图。当废弃轨道集遍历依次完毕后，修复也就结束了。但是，本题有一个极端情况，当某个城市被占领后，无法通过修复已废弃的轨道使得剩下的城市彼此连通。这样的话，修复代价为无穷大。

   程序如下：

// 1001.cpp : 定义控制台应用程序的入口点。
//




#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define N 501
#define INF 0x7fffffff
typedef struct{
int c1;
int c2;
int cost;
}Len;
bool cmp(Len a,Len b)
{
return a.cost<b.cost;
}


vector<Len> lens1,lens2;//lens1废弃的轨道集，lens2在用的轨道集
int root[N];


int findroot(int id)
{
if(root[id]==-1)//本节点就是根节点
return id;
int x=findroot(root[id]);//本语句的原因，两个连通图S1(根节点r1)、S2(根节点r2)合并，
//只是将r2的根节点设为r1，所以当S1，S2合并后，S2中的节点的根节点并未修改，
//当求S2中节点的根节点时，需要先找到r2,再通过r2找到r1
root[id]=x;//及时修改以上情况下S2中节点的根节点为人r1
return x;
}


vector<int> answerids;//存放结果
int maxcost=0;//当前修复代价的最大值
int main()
{
int n,m;
cin>>n>>m;
int c1,c2,cost,tag;
for(int i=0;i<m;++i)
{
cin>>c1>>c2>>cost>>tag;
//len[c1][c2]=len[c2][c1]=cost;
Len tmp;
tmp.c1=c1,tmp.c2=c2,tmp.cost=cost;
if(tag==0)
{
lens1.push_back(tmp);    //tag=0的边集
}
else{
lens2.push_back(tmp);   //tag=1的边集
}
}
sort(lens1.begin(),lens1.end(),cmp);//tag=0的边集排序
for(int i=1;i<=n;++i)  //当去掉i节点后，依据边集进行划分，划分成簇
{
for(int j=1;j<=n;++j)
root[j]=-1;
for(int k=0;k<lens2.size();++k)
{
if(lens2[k].c1==i||lens2[k].c2==i)
continue;
int c1=lens2[k].c1,c2=lens2[k].c2;
int root1=findroot(c1);
int root2=findroot(c2);
if(root1!=root2)
{
root[root2]=root1;
}
}
int cost=0;//删除本节点i后，修复所需要的代价
int num=0; //删除城市i后，彼此连通的城市集合个数，即簇个数
for(int s=1;s<=n;++s)//簇个数
{
if(s!=i&&root[s]==-1)
++num;
}
for(int t=0;t<lens1.size();++t)
{
if(num==1)   //城市簇只有一个，连通
break;
int c1=lens1[t].c1,c2=lens1[t].c2;
if(c1==i||c2==i)
continue;
int root1=findroot(c1);
int root2=findroot(c2);
if(root1!=root2)
{
cost+=lens1[t].cost;
root[root2]=root1;
--num;
}
}
if(num>1) //极端情况 删除该点后 剩下的点通过修复边也无法构成连通图，本段if语句注释掉后，将有一个case无法通过。
{
cost=INF;
}
if(cost>0&&cost>maxcost)
{
maxcost=cost;
answerids.erase(answerids.begin(),answerids.end());
answerids.push_back(i);
}
else if(cost>0&&cost==maxcost)
answerids.push_back(i);
}
if(answerids.empty())
cout<<"0";
else
for(int i=0;i<answerids.size();++i)
{
if(i!=0)
cout<<" ";
cout<<answerids[i];
}
return 0;
}