[网络流24题-2]cogs396魔术球问题

至于那个贪心的证明我是没整出来的。。。看了黑书，可能是我没有认真看吧。

最小路径点覆盖：用最少的边去覆盖尽可能多的点（全部）。

黑书上介绍了一个求最小路径点覆盖的方法，很值得借鉴，那就是每个点i转化为一个i和i′，当原图存在边(i,j)时，连边(i,j′)，求这个S−T割的最大二分图匹配，再用点数-这个值即为最小路径点覆盖。

为什么呢？因为假定原图每条边只对应一个点，那么n个点需要n条边去覆盖。每存在一条连了2个点的边就可以省去一条边，而这个二分图匹配能保证是互不有重叠点的边集的最大值，所以肯定最多能省去这么多条边；能省去这么多条边后自然省去每条边对应的那个点；因而用总点数-最大匹配即为答案。

具体到这个题，就是把两个和为完全平方数的两球连一条边，枚举，数据比较小，能过。而且我并不觉得设一个上界和下界去二分能提升多大的速度，所以直接用for枚举。

唯一注意的是，上一次枚举完的边还可以用的 要加的边只是所有点到多的点还要加的边。然后这样的话跑cogs的数据足够。。。。

然后还是要用匈牙利算法求最大匹配；judge函数用来判断是否和为平方数。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//AC
using namespace std;
const int maxn=10000;

vector g[maxn];
void addedge(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
}
int match[maxn];
bool book[maxn];
int n;
bool judge(int n)
{
    double nn=sqrt(n);
    if((int)n/nn==nn)
    {
        return true;
    }
    return false;
}

bool dfs(int v)
{
    for(unsigned i=0;i