USACO Agri-Net 3.1

用的kruskal求最小生成树，开始想着用一维数组判断是否存在环,后来一想不对,可能每个点都放连到,但是路径之间不连通...

还是得换二维,再就是set里判断元素相等是根据A<B==FALSE&&B<A==FALSE 要注意,不行就换multiset...

  1 /*
  2 
  3 ID: hubiao cave
  4 
  5 PROG: agrinet
  6 
  7 LANG: C++
  8 
  9 */
 10 
 11 
 12 
 13 
 14 #include<iostream>
 15 
 16 #include<fstream>
 17 #include<cstring>
 18 #include<string>
 19 
 20 #include<set>
 21 #include<utility>
 22 using namespace std;
 23 
 24 #define MAX 888888
 25 
 26 struct node
 27 {
 28     int w;
 29     pair<int,int> p;
 30 };
 31 
 32 bool operator <(const node&,const node&);
 33 bool operator ==(const node&,const node&);
 34 int main()
 35 
 36 {
 37 
 38     ifstream fin("agrinet.in");
 39     ofstream fout("agrinet.out");
 40     
 41     int A[102][102],B[102];
 42     int num;
 43     int temp;
 44     int res=0;
 45     multiset<node> sn;
 46 
 47     for(int i=0;i<=101;i++)
 48         memset(A[i],0,102*4);
 49 
 50     
 51   fin>>num;
 52 
 53       /*node n1,n2;
 54     n1.w=n2.w=4;
 55     n1.p.first=3;
 56     n1.p.second=6;
 57     n2.p.first=4;
 58     n2.p.second=5;
 59     int m=!(n1<n2||n2<n1);*/
 60 
 61     for(int i=1;i<=num;i++)
 62     {
 63         B[i]=1;
 64         for(int j=1;j<=num;j++)
 65         {
 66             fin>>temp;
 67             if(temp==0)
 68                 continue;
 69             else
 70             {
 71                 if((num-i+1)+j>num)
 72                 {
 73                 node n;
 74                 n.w=temp;
 75                 n.p.first=i;
 76                 n.p.second=j;
 77                 sn.insert(n);
 78                 }
 79             }
 80         }
 81     }
 82 
 83 
 84 
 85     for(set<node>::iterator it=sn.begin();it!=sn.end();it++)
 86     {
 87         if(A[it->p.first][it->p.second])
 88             continue;
 89         else
 90         {
 91             A[it->p.first][it->p.second]=1;
 92             A[it->p.second][it->p.first]=1;
 93             res+=it->w;
 94             for(int i=1;i<=num;i++)
 95             {
 96                 for(int j=1;j<=num;j++)
 97                 {
 98                     if(A[i][j]==1)
 99                     {
100                         for(int m=1;m<=num;m++)
101                             if(A[j][m])
102                                 A[i][m]=1;
103                     }
104                 }
105             }
106         }
107     }
108     fout<<res<<endl;
109 
110 
111     return 0;
112 
113 
114 }
115 bool operator < (const node& n1,const node&n2)
116 {
117     return n1.w<n2.w;
118 }