题目：
给一张无向图，求其所有spf节点
Sample Input
1 2 5 4 3 1 3 2 3 4 3 5 0 1 2 2 3 3 4 4 5 5 1 0 1 2 2 3 3 4 4 6 6 3 2 5 5 1 0 0
Sample Output
Network #1 SPF node 3 leaves 2 subnets Network #2 No SPF nodes Network #3 SPF node 2 leaves 2 subnets SPF node 3 leaves 2 subnets
思路：
（明知道这道题是用图算法的一些东西做的，明知道你丫还没看图算法呢，还特么碰。果然，卡了吧，该。）
遍历去掉每个节点，计算去掉该节点之后形成了多少个子网，即为结果。
方案：
先将所给一条条连接快排，得到网络内节点个数amount，从1遍历至amount，生成subnet数组，长度为amount+1：0 1-amount，计算会形成多少个子网。
代码：
1 void NetCheck(Net *tab,int con_cnt,int net_cnt) 2 { 3 int tmp; 4 int i; 5 for(i=0;i<=con_cnt-1;++i) 6 if(tab[i].bin>tab[i].end) 7 { 8 tmp=tab[i].bin; 9 tab[i].bin=tab[i].end; 10 tab[i].end=tmp; 11 } 12 qsort(tab,con_cnt,sizeof(Net),comp); 13 int amount=tab[con_cnt-1].end; 14 15 int node,sub_net_cnt,start,cur,spf_mark=0,j; 16 int *subnet=(int *)malloc(sizeof(int)*(amount+1)); 17 printf("Network #%d\n",net_cnt); 18 for(node=1;node<=amount;++node) 19 { 20 if(node==1) 21 start=2; 22 else 23 start=1; 24 sub_net_cnt=0; 25 memset(subnet,0,sizeof(int)*(amount+1)); 26 subnet[node]=-1; 27 while(start<=amount) 28 { 29 subnet[start]=++sub_net_cnt; 30 for(i=0;i<=con_cnt-1;++i) 31 { 32 if(tab[i].bin==node||tab[i].end==node) 33 continue; 34 if(subnet[tab[i].bin]==sub_net_cnt) 35 { 36 if(subnet[tab[i].end]!=0&&subnet[tab[i].end]!=sub_net_cnt) 37 { 38 --sub_net_cnt; 39 for(j=1;j<=amount;++j) 40 if(subnet[j]==subnet[tab[i].end]) 41 subnet[j]=sub_net_cnt; 42 } 43 subnet[tab[i].end]=sub_net_cnt; 44 } 45 else if(subnet[tab[i].end]==sub_net_cnt) 46 { 47 if(subnet[tab[i].bin]!=0&&subnet[tab[i].bin]!=sub_net_cnt) 48 { 49 --sub_net_cnt; 50 for(j=1;j<=amount;++j) 51 if(subnet[j]==subnet[tab[i].end]) 52 subnet[j]=sub_net_cnt; 53 } 54 subnet[tab[i].bin]=sub_net_cnt; 55 } 56 } 57 while(start<=amount&&subnet[start]!=0) 58 ++start; 59 } 60 if(sub_net_cnt>1) 61 { 62 spf_mark=1; 63 printf(" SPF node %d leaves %d subnets\n",node,sub_net_cnt); 64 } 65 } 66 if(spf_mark==0) 67 printf(" No SPF nodes\n"); 68 } 69 70 int comp(const void *a,const void *b) 71 { 72 return ((Net *)a)->end-((Net *)b)->end; 73 }
记录：
我勒个去的到目前这版，在基本代至上所进行过的修改：修改了输出规格（每两份网络中间空一行而不是每份网络之后空一行），修改了排序基准以获得最大网络节点号，但还是找不到错误在哪里，结果一直是wrong answer……我决定先放在这里了，恶心了。
心得：
革命尚未成功，同志们回头努力。