Description
圣诞节将至。一年一度的难题又摆在wyx面前——如何给妹纸送礼物。
wyx的后宫有n人，这n人之间有着复杂的关系网，相互认识的人有m对。wyx想要量化后宫之间的亲密度，于是准备给每对认识关系估一个亲密度。亲密度是个正整数，值越大说明越亲密。当然有可能有些后宫之间不直接认识，为此wyx定义了一个值f(i,j)，代表从第i个后宫开始不断经过认识的人到j，经过的亲密度最小的一对关系的最大值。不过也有可能有些后宫的朋友圈互相独立，怎么也没法通过认识的人互相到达，那么f(i,j)就为-1。
举个例子，wyx的后宫有4人，编号为1~4。后宫1和2之间的亲密度为3，后宫2和3之间的亲密度为4，后宫1和3之间的亲密度为2，后宫4由于不明原因被孤立了。那么f(1,2)=f(1,3)=3，f(2,3)=4，f(1,4)=f(2,4)=f(3,4)=-1。
wyx认为了解后宫之间的亲密程度对于他选择礼物有着很重大的意义，于是他找了几个路人，测出了所有后宫之间的f(i,j)值。不过wyx怀疑路人在坑爹，他想知道，是否能找到一组后宫之间的亲密度方案满足路人测出的f(i,j)值？由于他还要去把妹，这个问题就交给你了。
Input
第一行一个正整数T，代表数据组数。
接下来T组数据，每组数据第一行两个正整数n、m，代表点数和边数。
接下来m行，每行两个正整数代表一条边。
接下来n行每行n个整数，代表所有的f(i,j)值。
Output
对于每组数据，输出 "Yes" 或者 "No"。（详细参看样例输出）
Sample Input
4 5
1 2
1 3
1 4
2 3
2 4
0 5 5 5
5 0 5 5
5 5 0 4
5 5 4 0
4 4
1 2
1 3
2 3
2 4
0 4 4 4
4 0 4 5
4 4 0 4
4 5 4 0
4 2
1 2
2 3
0 3 3 -1
3 0 4 -1
3 4 0 -1
-1 -1 -1 0
Sample Output
Case #2: Yes
Case #3: Yes
HINT
数据范围
T ≤ 30
n ≤ 1000
m ≤ 300000
f(i,j)=-1 或者 1 ≤ f(i,j) ≤ 32767
注意输入量奇大无比！
题解:
看到亲密度的定义，很容易想到最大生成树。
则题意是检验一棵最大生成树是否合法。
把亲密度从大到小排序（为了省时间，可以用桶排序挂链），同时处理亲密度相同的每一对关系。
若某一对人在之前已经被放在一个并查集里（即实际亲密度应该比给出的高），则不合法。
对于要处理的每一对关系，把相应的并查集之间所有的边连上。连好后，检查这些关系是否被满足。
对于-1的关系，则用类似的方法特殊处理。
为了能够访问并查集的每一个节点，并查集采用按值合并以及前向星记录子节点，而不是路径压缩。
输入量并不怎么大，不用快读也可以。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int c[2000],cc[40000],bb[1000001][3],b[2000],fa[2000],size[2000],mp[1001][1001],mp2[1001][1001],lb[1000001][3]; 4 int n,m,x,nn,flag,mm,t; 5 bool ss2(int x,int y) 6 { 7 if(mp[x][y]==1)return 1; 8 for(int i=c[y];i;i=b[i])if(ss2(x,i))return 1; 9 return 0; 10 } 11 bool ss1(int x,int y) 12 { 13 if(ss2(x,y))return 1; 14 for(int i=c[x];i;i=b[i])if(ss1(i,y))return 1; 15 return 0; 16 } 17 int get(int x) 18 { 19 while(fa[x]!=x)x=fa[x]; 20 return x; 21 } 22 int main() 23 { 24 scanf("%d",&t); 25 for(int tt=1;tt<=t;tt++) 26 { 27 scanf("%d%d",&n,&m); flag=0; 28 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=0,mp2[i][j]=32768; 29 for(int i=0;i<=32767;i++)cc[i]=0; 30 for(int i=1;i<=m;i++) 31 { int j,k; scanf("%d%d",&j,&k); mp[j][k]=1; mp[k][j]=1; } 32 for(int i=1;i<=n;i++) 33 for(int j=1;j<=n;j++) 34 { 35 scanf("%d",&x); if(x<0)x=0; if(i==j)continue; 36 nn++; bb[nn][1]=i; bb[nn][2]=j; bb[nn][0]=cc[x]; cc[x]=nn; 37 } 38 for(int i=1;i<=n;i++)fa[i]=i,size[i]=1,c[i]=0; 39 for(int num=32767;num>=0;num--) 40 { 41 mm=0; 42 for(int i=cc[num];i;i=bb[i][0]) 43 { 44 int x=get(bb[i][1]),y=get(bb[i][2]); 45 if(x==y){ flag=1; break; } 46 if(x>y)swap(x,y); 47 if(mp2[x][y]!=num) 48 { 49 mp2[x][y]=num; mm++; lb[mm][0]=0; lb[mm][1]=x; lb[mm][2]=y; 50 } 51 } 52 for(int i=1;i<=mm;i++)if(ss1(lb[i][1],lb[i][2]))lb[i][0]=1; 53 for(int i=1;i<=mm;i++)if(lb[i][0]==1) 54 { 55 if(num==0){ flag=1; break; } 56 int x=get(lb[i][1]),y=get(lb[i][2]); 57 if(x!=y) 58 { 59 if(size[x]<size[y])swap(x,y); 60 size[x]=size[x]+size[y]; fa[y]=x; b[y]=c[x]; c[x]=y; 61 } 62 } 63 for(int i=1;i<=mm;i++)if(lb[i][0]==0) 64 { 65 if(num==0)continue; 66 int x=get(lb[i][1]),y=get(lb[i][2]); 67 if(x!=y){ flag=1; break; } 68 } 69 if(flag==1)break; 70 } 71 if(flag==0)printf("Case #%d: Yes ",tt); 72 else printf("Case #%d: No ",tt); 73 } 74 }