题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3275
这题还是挺有意思的!
首先,肯定一眼能看出来是最小割
然后就是建图了。
1)暴力方法,拆点:http://hzwer.com/2864.html ←这样搞虽然不优雅,但普适性更强?←这样做是错的,详见UPD
2)优雅的方法:写个程序试一试,发现在1000以内的冲突的a,b一定是一奇一偶,于是搞成二分图
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 3000+9; const int M = 1000000; const int INF = 1000000000; int n,arr[N],head[N],nxt[M],to[M],flow[M],cur[N],dis[N],S,T,vout; queue<int> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } #define sqr(x) ((x)*(x)) int GCD(int a, int b) {return b?GCD(b,a%b):a;} inline void Add_Edge(int u, int v, int f) { static int TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); dis[S] = 0; que.push(S); while (!que.empty()) { int w = que.front(); que.pop(); for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) dis[to[i]] = dis[w] + 1, que.push(to[i]); } return ~dis[T]; } int DFS(int w, int f) { if (w == T) return f; else { int ret = 0; for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp; if (!f) break; } return ret; } } inline int Dinic(){ int ret = 0; while (BFS()) { memcpy(cur,head,sizeof(head)); ret += DFS(S,INF); } return ret; } int main(){ n = read(); S = 0; T = N - 1; for (int i=1;i<=n;i++) arr[i] = read(), vout += arr[i]; for (int i=1;i<=n;i++) if (arr[i]%2) Add_Edge(S,i,arr[i]); else Add_Edge(i,T,arr[i]); for (int i=1;i<=n;i++) if (arr[i]%2) for (int j=1,w=sqr(arr[i])+sqr(arr[j]);j<=n;j++,w=sqr(arr[i])+sqr(arr[j])) if (GCD(arr[i],arr[j])==1 && sqr(int(sqrt(w)+1e-7))== w) Add_Edge(i,j,INF); printf("%d\n",vout-Dinic()); return 0; }
—– UPD 2016.9.17 —–
给一下证明:
首先同为偶数肯定不成立。
对于同为奇数的情况:
(2a-1)^2+(2b-1)^2=c^2
c^2=4(a(a-1)+b(b-1))+2
不难发现c^2中只有一个2,没有两个2
所以c不可能为整数
得证.
—– UPD 2016.9.18 —–
今天突然想到,如果hzwer那种建模可以在一般图中推广的话
那我们还要带花树干嘛?
所以这题黄学长没证二分图就艹过去了,这完全是运气好啊!
但再仔细想一想,如果是带花树的题,岂不是可以尝试这样去骗分?
I’d have to check with you here. Which is not something I normally do! I take pleasure in studying a submit that will make individuals think. Also, thanks for allowing me to comment!
Good write-up, I’m regular visitor of one’s blog, maintain up the nice operate, and It is going to be a regular visitor for a long time.