BZOJ 3624 [Apio2008]免费道路：并查集 + 生成树 + 贪心【恰有k条特殊路径】

  1 #include   2 #include   3 #include string.h>
  4 #include 
  5 #include   6 #define MAX_N 20005
  7 
  8 using namespace std;
  9 
 10 struct Edge
 11 {
 12     int sour;
 13     int dest;
 14     int len;
 15     Edge(int _sour,int _dest,int _len)
 16     {
 17         sour=_sour;
 18         dest=_dest;
 19         len=_len;
 20     }
 21     Edge(){}
 22     friend bool operator const Edge &a,const Edge &b)
 23     {
 24         return a.lenb.len;
 25     }
 26 };
 27 
 28 int n,m,k;
 29 int par[MAX_N];
 30 bool failed=false;
 31 vector edge;
 32 vector est;
 33 vector ans;
 34 
 35 void read()
 36 {
 37     cin>>n>>m>>k;
 38     int a,b,c;
 39     for(int i=0;i)
 40     {
 41         cin>>a>>b>>c;
 42         edge.push_back(Edge(a,b,c));
 43     }
 44 }
 45 
 46 void init_union_find()
 47 {
 48     for(int i=1;i)
 49     {
 50         par[i]=i;
 51     }
 52 }
 53 
 54 int find(int x)
 55 {
 56     return par[x]==x?x:par[x]=find(par[x]);
 57 }
 58 
 59 void unite(int x,int y)
 60 {
 61     int px=find(x);
 62     int py=find(y);
 63     if(px==py) return;
 64     par[px]=py;
 65 }
 66 
 67 bool same(int x,int y)
 68 {
 69     return find(x)==find(y);
 70 }
 71 
 72 void max_tree()
 73 {
 74     init_union_find();
 75     sort(edge.begin(),edge.end());
 76     int cnt=0;
 77     for(int i=edge.size()-1;i>=0;i--)
 78     {
 79         Edge temp=edge[i];
 80         if(!same(temp.sour,temp.dest))
 81         {
 82             cnt++;
 83             unite(temp.sour,temp.dest);
 84             if(temp.len==0) est.push_back(temp);
 85         }
 86     }
 87     if(cnt!=n-1 || est.size()>k) failed=true;
 88 }
 89 
 90 void min_tree()
 91 {
 92     init_union_find();
 93     int cnt=0;
 94     int spe=0;
 95     for(int i=0;i)
 96     {
 97         Edge temp=est[i];
 98         cnt++;
 99         spe++;
100         ans.push_back(temp);
101         unite(temp.sour,temp.dest);
102     }
103     for(int i=0;i)
104     {
105         Edge temp=edge[i];
106         if(!same(temp.sour,temp.dest))
107         {
108             if(temp.len==0)
109             {
110                 if(spek)
111                 {
112                     cnt++;
113                     spe++;
114                     ans.push_back(temp);
115                     unite(temp.sour,temp.dest);
116                 }
117             }
118             else
119             {
120                 cnt++;
121                 ans.push_back(temp);
122                 unite(temp.sour,temp.dest);
123             }
124         }
125     }
126     if(cnt!=n-1 || spe!=k) failed=true;
127 }
128 
129 void solve()
130 {
131     max_tree();
132     min_tree();
133 }
134 
135 void print()
136 {
137     if(failed)
138     {
139         cout"no solution"endl;
140         return;
141     }
142     for(int i=0;i)
143     {
144         Edge temp=ans[i];
145         cout" "" "endl;
146     }
147 }
148 
149 int main()
150 {
151     read();
152     solve();
153     print();
154 }