[BeiJing wc2012]连连看（建模，最小费用最大流）

前言

突然发现自己在图论①被dalao吊着打。。。

Solution

看到数据范围1000，感觉可以直接枚举连边，然后新建两个点就好了。
注意要拆点，不然可能会死循环（过来人）

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=2010,M=3000010,Inf=1e9+10;
int s=0,t,MaxFlow,MinCost,a,b;
class Graph{
private:
	int front[N],cnt,nxt[M<<1],to[M<<1],w[M<<1],c[M<<1],dis[N],vis[N],fa[N],from[N];
	bool SPFA(){
		queue<int >Q;while(!Q.empty())Q.pop();
		Q.push(s);memset(dis,127,sizeof(dis));vis[s]=1;dis[s]=0;
		while(!Q.empty()){
			int u=Q.front();Q.pop();vis[u]=0;
			for(int i=front[u];i!=-1;i=nxt[i]){
				int v=to[i];
				if(w[i] && dis[v]>dis[u]+c[i]){
					dis[v]=dis[u]+c[i];from[v]=i;fa[v]=u;
					if(!vis[v]){
						vis[v]=1;Q.push(v);
					}   
				}
			}
		}
		return dis[t+1]!=dis[t];
	}
public:
	void Add(int u,int v,int val,int f){to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;c[cnt]=f;++cnt;}
	void init(){memset(front,-1,sizeof(front));cnt=0;}
	void Solve(){
		while(SPFA()){
			int d=Inf;
			for(int i=t;i!=s;i=fa[i])d=min(d,w[from[i]]);
			MaxFlow+=d;MinCost+=d*dis[t];
			for(int i=t;i!=s;i=fa[i]){w[from[i]]-=d;w[from[i]^1]+=d;}
		}
	}
}MfMc;
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
int main(){
	MfMc.init();
	a=gi();b=gi();s=0;t=2*b+1;
	for(int i=a;i<=b;i++){
		MfMc.Add(i+b,t,1,0);MfMc.Add(t,i+b,0,0);
		MfMc.Add(s,i,1,0);MfMc.Add(i,s,0,0);
		for(int j=a;j<i;j++){
			int sq=i*i-j*j,sqr=sqrt(sq);
			if(sqr*sqr==sq && gcd(sqr,j)==1){
				MfMc.Add(j,i+b,1,-(i+j));
				MfMc.Add(i+b,j,0,(i+j));
				MfMc.Add(i,j+b,1,-i-j);
				MfMc.Add(j+b,i,0,i+j);
			}
		}
	}
	MfMc.Solve();
	printf("%d %d
",MaxFlow/2,-MinCost/2);
	return 0;
}