图论与数据结构
上次Gardon的迷宫城堡小希玩了很久（见ProblemB），现在她也想设计一个迷宫让Gardon来走。
但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，
就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B
，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通
（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路
Input
输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。
房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
Output
对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。
Sample Input
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
Sample Output
Yes
Yes
No
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int p[N];
int st[N];
void init()
{
for(int i=1;i<=N;i++)
{
p[i]=i;
st[i]=0;
}
}
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
int fa=find(a),fb=find(b);
if(fa!=fb)
{
p[fb]=fa;
}
}
int main()
{
int x,y;
while(scanf("%d%d",&x,&y))
{
if(x==-1&&y==-1)break;
init();
int flag=0;
while(1)
{
if(x==0&&y==0)break;
if(find(x)==find(y))
{
flag=1;
}
merge(x,y);
st[x]=st[y]=1;
scanf("%d%d",&x,&y);
}
if(flag==1)
{
printf("No\n");
continue;
}
int sum=0;
for(int i=1;i<=N;i++){
if(st[i]&&p[i]==i)
{
sum++;
}
}
if(sum>1)
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
return 0;
}
王先生想要几个男孩帮他做一个项目。因为这个项目相当复杂，男孩来的越多越好。
当然有一定的要求。 王先生选了一间足够容纳孩子们的房间。未被选中的男孩必须立即离开房间。
房间里有10000000个男孩，一开始的数字从1到10000000。在王先生选择之后
，他们中任何两个仍然在这个房间里的人都应该是朋友（直接或间接），
否则就只剩下一个男孩了。考虑到所有的直接朋友对，你应该决定最好的方式。
Input
输入的第一行包含一个整数n（0≤ N≤ 100000）-直接朋友对的数量。下面的n行分别包含一对数字a和B，
由一个空格分隔，表示a和B是直接的朋友(A.≠ B、 1 ≤ A、 B ≤ 10000000)
Output
一行中的输出正好包含一个整数，等于王先生可能保留的男孩的最大数量。
Sample Input
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e7+10;
int p[N],size1[N];
int n;
void init()
{
for(int i=1;i<=N;i++)
{
p[i]=i;
size1[i]=1;
}
}
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
int fa=find(a),fb=find(b);
if(fa!=fb)
{
p[fb]=fa;
size1[fa]+=size1[fb];
}
}
int main()
{
int a,b;
while(~scanf("%d",&n))
{
if(n==0)
{
puts("1");
continue;
}
init();
int m=0;
while(n--)
{
scanf("%d%d",&a,&b);
if(m<a)m=a;
if(m<b)m=b;
merge(a,b);
}
int max1=-1;
for(int i=1;i<=m;i++)
{
if(p[i]==i)
{
max1=max(max1,size1[i]);
}
}
printf("%d\n",max1);
}
return 0;
}
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通
（但不一定有直接的公路相连，只要能间接通过公路可达即可）。
现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，
以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )
；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，
分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。
当N为0时输入结束。
Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
Sample Input
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0
Sample Output
3
1
0
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N=110;
int g[N][N],dist[N];
bool st[N];
int n;
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
if(i&&dist[t]==INF)return INF;
if(i)res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)break;
memset(g,0x3f,sizeof g);
memset(st,false,sizeof st);
int len=n*(n-1)/2;
int a,b,w,f;
for(int i=1;i<=len;i++)
{
scanf("%d%d%d%d",&a,&b,&w,&f);
if(!f)
{
g[a][b]=g[b][a]=min(g[a][b],w);
}
else
{
g[a][b]=g[b][a]=0;
}
}
printf("%d\n",prim());
}
return 0;
}
2100年，由于海平面上升，大部分城市消失了。虽然一些幸存下来的城市仍然与其他城市相连
，但它们中的大多数已经断开了连接。政府想修建一些道路再次连接所有这些城市，但他们不想花费太多的钱。
Input
第一行包含测试用例的数量。每个测试用例从三个整数开始：n、m和k
。n（3 <= n <= 500）表示幸存城市的数量，m（0 <= m <= 25000）表示可以选择连接城市的道路数量
，k（0 <= k <= 100）表示仍然连接的城市数量。为了方便起见，这些城市从1号到n号。
然后跟随m行，每行包含三个整数p、q和c（0 <= c <=1000），这意味着需要c来连接p和q。
然后沿着k行，每行以整数t（2 <= t <= n）开始，表示连接的城市数量。然后t整数表示这些城市的id。
Output
对于每种情况，输出你需要的最少的钱，如果不可能，只输出-1。
Sample Input
1
6 4 3
1 4 2
2 6 1
2 3 5
3 4 33
2 1 2
2 1 3
3 4 5 6
Sample Output
1
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N=510;
int g[N][N],dist[N];
bool st[N];
int city[N];
int n,m,k;
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
if(i&&dist[t]==INF)return INF;
if(i)res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(g,0x3f,sizeof g);
memset(st,false,sizeof st);
int p,q,c;
while(m--)
{
scanf("%d%d%d",&p,&q,&c);
g[p][q]=g[q][p]=min(g[p][q],c);
}
while(k--)
{
int t;
scanf("%d",&t);
memset(city,0,sizeof city);
for(int i=1;i<=t;i++)
{
scanf("%d",&city[i]);
}
for(int i=1;i<=t;i++)
{
for(int j=i+1;j<=t;j++)
{
g[city[i]][city[j]]=g[city[j]][city[i]]=0;
}
}
}
int res=prim();
if(res==INF)printf("-1\n");
else
printf("%d\n",res);
}
return 0;
}
