可以看做一些物品中某些互相排斥求最大价值。如果这是个二分图的话,就很容易用最小割了。
观察其给出的条件间是否有什么联系。如果两个数都是偶数,显然满足条件二;而若都是奇数,则满足条件一,因为式子列出来发现一定不能写成完全平方数。那么这就是个二分图了。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1010#define inf 1000000000#define S 0#define T 1001int n,p[N],a[N],b[N],ans=0,t=-1;int d[N],cur[N],q[N];struct data{ int to,nxt,cap,flow;}edge[N*N<<1];void addedge(int x,int y,int z){ t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=0,p[x]=t; t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=0,edge[t].flow=0,p[y]=t;}bool bfs(){ memset(d,255,sizeof(d));d[S]=0; int head=0,tail=1;q[1]=S; do { int x=q[++head]; for (int i=p[x];~i;i=edge[i].nxt) if (d[edge[i].to]==-1&&edge[i].flow