bzoj2661: [BeiJing wc2012]连连看 最小费用流

这道题正统的做法应该是进行黑白染色（因为我们发现 $x,y$ 满足二分图的性质）   

这里写了一个不会证明正确性的解法.   

一般来说，这种相消/要求互质什么的一般都要转换成二分图来解决. 

code: 

#include <bits/stdc++.h>  
#define N 20008   
#define inf 10000000 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int s,t,n=1000,m,flow,ans;      
namespace mcmf      
{     
    int d[N],a[N],flow2[N],inq[N];      
    struct Edge
    {
        int u,v,cap,cost;  
        Edge(int u=0,int v=0,int cap=0,int cost=0):u(u),v(v),cap(cap),cost(cost){}  
    };  
    queue<int>q;     
    vector<int>G[N];
    vector<Edge>edges;      
    inline void add(int u,int v,int cap,int cost) 
    {   
        edges.push_back(Edge(u,v,cap,cost));   
        edges.push_back(Edge(v,u,0,-cost));   
        int p=edges.size();   
        G[u].push_back(p-2);  
        G[v].push_back(p-1);  
    }
    int spfa() 
    {
        for(int i=0;i<N;++i) d[i]=flow2[i]=inf;  
        memset(inq,0,sizeof(inq));   
        d[s]=0,inq[s]=1,q.push(s);         
        while(!q.empty()) 
        {
            int u=q.front(); q.pop(),inq[u]=0;      
            for(int i=0;i<G[u].size();++i) 
            {
                Edge e=edges[G[u][i]];    
                if(e.cap>0&&d[e.v]>d[u]+e.cost) 
                {
                    d[e.v]=d[u]+e.cost;   
                    flow2[e.v]=min(flow2[u],e.cap);    
                    a[e.v]=G[u][i];   
                    if(!inq[e.v]) 
                    {
                        inq[e.v]=1;   
                        q.push(e.v);   
                    }
                }
            }
        }  
        if(d[t]==inf) return 0;       
        int f=flow2[t];   
        flow+=f;  
        int u=edges[a[t]].u;   
        edges[a[t]].cap-=f;  
        edges[a[t]^1].cap+=f;   
        while(u!=s) 
        {
            edges[a[u]].cap-=f;   
            edges[a[u]^1].cap+=f;   
            u=edges[a[u]].u;      
        }           
        ans+=d[t]*f;       
        return 1;     
    }
    inline int maxflow() { while(spfa()); return flow; }   
    inline int getcost() { return ans; }   
};  
int I1(int x) { return x; } 
int I2(int x) { return x+n; }     
int main() 
{
    // setIO("input"); 
    int L,R;  
    scanf("%d%d",&L,&R);                      
    s=0,t=R<<1+1;    
    for(int i=L;i<=R;++i) 
    {
        mcmf::add(s,I1(i),1,0);
        mcmf::add(I2(i),t,1,0);  
    }    
    for(int i=L;i<=R;++i) 
    {
        for(int j=i+1;j<=R;++j) 
        {   
            int p=j*j-i*i;   
            int k=sqrt(p);   
            if(k*k==p&&__gcd(k,i)==1) 
            {                             
                mcmf::add(I1(j),I2(i),1,-i-j); 
                mcmf::add(I1(i),I2(j),1,-i-j);   
            }
        }
    }
    printf("%d ",mcmf::maxflow()/2);   
    printf("%d
",-mcmf::getcost()/2);  
    return 0; 
}