至于那個貪心的證明我是沒整出來的。。。看了黑書，可能是我沒有認(rèn)真看吧。

最小路徑點覆蓋：用最少的邊去覆蓋盡可能多的點（全部）。

黑書上介紹了一個求最小路徑點覆蓋的方法，很值得借鑒，那就是每個點i轉(zhuǎn)化為一個i和i′，當(dāng)原圖存在邊(i,j)時，連邊(i,j′)，求這個S?T割的最大二分圖匹配，再用點數(shù)-這個值即為最小路徑點覆蓋。

為什么呢？因為假定原圖每條邊只對應(yīng)一個點，那么n個點需要n條邊去覆蓋。每存在一條連了2個點的邊就可以省去一條邊，而這個二分圖匹配能保證是互不有重疊點的邊集的最大值，所以肯定最多能省去這么多條邊；能省去這么多條邊后自然省去每條邊對應(yīng)的那個點；因而用總點數(shù)-最大匹配即為答案。

具體到這個題，就是把兩個和為完全平方數(shù)的兩球連一條邊，枚舉，數(shù)據(jù)比較小，能過。而且我并不覺得設(shè)一個上界和下界去二分能提升多大的速度，所以直接用for枚舉。

唯一注意的是，上一次枚舉完的邊還可以用的 要加的邊只是所有點到多的點還要加的邊。然后這樣的話跑cogs的數(shù)據(jù)足夠。。。。

然后還是要用匈牙利算法求最大匹配；judge函數(shù)用來判斷是否和為平方數(shù)。

代碼

#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