BZOJ 3624: [Apio2008]免费道路

3624: [Apio2008]免费道路

Time Limit: 2 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 1201  Solved: 469
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1

Sample Output

3 2 0
4 3 0
5 3 1
1 2 1

HINT

Source

[Submit][Status][Discuss]

哎呀，这题好气啊，明明不难的，就是想不到啊，还是我太蒟蒻了啊。

题意要求我们求出一棵生成树，但是这次限制的不是权值大小，而是在一个给定的边集的子集中选出恰好K条边加入生成树，输出任意一种方案即可，SPJ。

这个其实很简单，你就先紧着子集里的边加，做Kruskal，求出一棵生成树（也许只能做出一棵生成森林），这是你保证了子集中选出的边>=K（如果小于K那就是无解啦），这时先用子集外的边填补漏洞，把森林补成树（补不成就是无解啦），然后再不断尝试加入子集外的边，显然加入之后会有环，那么替换掉环上的一条子集边即可（如果环上有的话），这个用LCT维护就好了，反正N<=20000是吧。

其实上面只是开玩笑的，如果你真的像我一开始这么想，看到Time Limit你就绝望了，23333——手动滑稽

正解是先紧着子集外的边加，造一个森林（能是树最好啦），然后用子集内的边补上不连通的位置。如果不能补成树或使用的子集边>K，那么就是无解。那么此时用来填补非子集边无法做到的联通性的边（就是刚才选出来的子集边）是一定要选的（并非必须边，但是一定存在一组可行解包含它们）。那么先选上这些，下面我们一定可以用非子集边把图连成生成树了，但是可能子集边还不到K，那就再随便选几个啦，然后再用非子集填补空缺。

 #include <cstdio>

 const int mxn = ;
 const int mxm = ;

 int n, m, k;

 struct edge
 {
     int x, y, c;
 }e[mxm];

 int fa[mxn];

 int find(int u)
 {
     return u == fa[u] ? u : fa[u] = find(fa[u]);
 }

 bool vis[mxm];

 signed main(void)
 {
     scanf("%d%d%d", &n, &m, &k);

     for (int i = ; i <= m; ++i)
         scanf("%d%d%d",
             &e[i].x,
             &e[i].y,
             &e[i].c);

     bool possible = true;

     {
         int cnt = , root;

         for (int i = ; i <= n; ++i)fa[i] = i;

         for (int i = ; i <= m; ++i)
             if (e[i].c)
             {
                 int fx = find(e[i].x);
                 int fy = find(e[i].y);

                 if (fx != fy)
                     fa[fx] = fy;
             }

         for (int i = ; i <= m; ++i)
             if (!e[i].c)
             {
                 int fx = find(e[i].x);
                 int fy = find(e[i].y);

                 if (fx != fy)
                     fa[fx] = fy, ++cnt, vis[i] = true;
             }

         if (cnt > k)
             possible = false;

         root = find();

         for (int i = ; i <= n; ++i)
             if (find(i) != root)
                 possible = false;

         k -= cnt;
     }

     if (!possible)
         return puts("no solution"), ;

     {
         for (int i = ; i <= n; ++i)fa[i] = i;

         for (int i = ; i <= m; ++i)
             if (vis[i])
             {
                 int fx = find(e[i].x);
                 int fy = find(e[i].y);

                 fa[fx] = fy;
             }

         for (int i = ; i <= m; ++i)
             if (!e[i].c && !vis[i] && k)
             {
                 int fx = find(e[i].x);
                 int fy = find(e[i].y);

                 if (fx != fy)
                     fa[fx] = fy, vis[i] = true, --k;
             }

         for (int i = ; i <= m; ++i)
             if (e[i].c)
             {
                 int fx = find(e[i].x);
                 int fy = find(e[i].y);

                 if (fx != fy)
                     fa[fx] = fy, vis[i] = true;
             }
     }

     for (int i = ; i <= m; ++i)
         if (vis[i])printf("%d %d %d\n", e[i].x, e[i].y, e[i].c);
 }

@Author: YouSiki