## 【HDU 5772】String problem

### 解题报告

1. 子序列看成子串
2. 值域范围$0 \sim 9$看漏

## 【日常小测】cut

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;

struct Data{
int u,v,val;
inline Data() {}
inline Data(int a, int b, int c):u(a),v(b),val(c) {}
inline bool operator < (const Data &B) const {
return val > B.val;
}
}p[N*N*N];

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;
}

inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
}

int cal(int w, int f, int pur, int mn) {
if (w == pur) return mn;
if (to[i] != f) {
tmp = cal(to[i], w, pur, min(mn, cost[i]));
if (~tmp) return tmp;
}
} return -1;
}

int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}

int main() {
for (int i=1,v;i<=n;i++) {
fa[i] = i;
for (int j=1;j<=n;j++) {
p[++tot] = Data(i, j, v);
}
}
sort(p+1, p+1+tot);
for (int i=1;i<=tot;i++) {
int u=p[i].u, v=p[i].v, val=p[i].val;
if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
else fa[find(u)] = fa[v], AddEdge(u, v, val);
}
cout<<n-1<<endl;
for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
return 0;
}


## 【TopCoder SRM558】Surrounding Game

### 解题报告

$j$ 是点 $i$ 拆出来的点， $a$ 、 $b$ 、 $c$ 、 $d$ 是与i点相邻的点拆出来的点

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000;
const int M = 100000;
const int INF = 1e9;

int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1,0};

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

class SurroundingGame {
int n,m,E,vout;
public:
int maxScore(vector<string> cost, vector<string> benefit) {
init();
m = cost.size();
n = cost[0].size();
for (int j=0;j<m;j++) {
for (int i=0;i<n;i++) {
vout += Val(benefit[j][i]);
}
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (i + j & 1) {
for (int k=1,x,y;k<=4;k++) {
x = i + dx[k];
y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= m) {
}
}
} else {
}
}
}
return vout - Dinic.MaxFlow();
}
private:
inline void init() {
E = 1; S = vout = 0; T = N - 1;
}
inline void Add_Edge(int u, int v, int f = INF) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}
inline int id(int x, int y, int t) {
return ((y-1) * n + (x-1)) * 2 + t;
}
inline int Val(char c) {
if ('A' <= c && c <= 'Z') return c - 29;
if ('a' <= c && c <= 'z') return c - 87;
if ('0' <= c && c <= '9') return c - 48;
}
};


## 【BZOJ 3144】[HNOI2013] 切糕

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 70000;
const int M = N << 2;
const int INF = 1e9;

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

inline void Add_Edge(int u, int v, int f = INF) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

char c=getchar(); int f=1,ret=0;
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;
}

inline int id(int x, int y, int z) {
return ((y - 1) * q + x - 1) * (r + 1) + z;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

int main() {
S = 0; T = N - 1;
for (int z=1;z<=r;z++) {
for (int y=1;y<=p;y++) {
for (int x=1,v;x<=q;x++) {
for (int k=0,X,Y;k<4;k++) {
X = x + dx[k];
Y = y + dy[k];
if (1 <= X && X <= q && 1 <= Y && Y <= p) {
if (z > d) Add_Edge(id(x,y,z), id(X,Y,z-d));
if (z+d+1 <= r) Add_Edge(id(X,Y,z+d+1), id(x,y,z));
}
}
}
}
}
for (int x=1;x<=q;x++) {
for (int y=1;y<=p;y++) {
}
}
printf("%d\n",Dinic.MaxFlow());
return 0;
}


## 【BZOJ 3894】文理分科

1. 选理的费用
2. 同选理的费用

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000+9;
const int M = 300000+9;
const int INF = 1e9;

int dx[]={1,0,-1,0},dy[]={0,1,0,-1},vout;

char c=getchar(); int f=1,ret=0;
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;
}

inline void Add_Edge(int u, int v, int f = INF) {
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = f;
to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = 0;
}

inline int id(int x, int y, int t) {
return n * m * (t - 1) + (y - 1) * n + x;
}

class MaxFlow{
int cur[N],dis[N];
queue<int> que;
public:
inline int solve() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

int main() {
S = 0; T = N - 1;
for (int j=1,tmp;j<=m;j++)
for (int i=1;i<=n;i++)
for (int j=1,tmp;j<=m;j++)
for (int i=1;i<=n;i++)
for (int j=1,tmp;j<=m;j++)
for (int i=1;i<=n;i++)
for (int j=1,tmp;j<=m;j++)
for (int i=1;i<=n;i++)
for (int j=1,w=0;j<=m;j++) {
for (int i=1;i<=n;i++) {
for (int k=0,x,y;k<4;k++) {
x = i + dx[k];
y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= m) {
}
}
}
}
printf("%d\n",vout-Dinic.solve());
return 0;
}


## 【TopCoder SRM590】Fox And City

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000;
const int M = 500000;
const int INF = 1e9;

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

class FoxAndCity {
int dis[100][100];
public:
int minimalCost(vector<string> linked, vector<int> want) {
init();
n = want.size();
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (linked[i][j] == 'Y') dis[i+1][j+1] = 1;
else dis[i+1][j+1] =  INF;
}
}
Floyd();
for (int i=2;i<=n;i++)
MX[i] = dis[1][i];
init(); S = 0; T = N - 1;
for (int i=2;i<=n;i++) {
for (int j=1;j<=MX[i];j++) {
for (int k=2;k<=n;k++) {
if (i != k && dis[i][k] == 1 && j > 1) {
}
}
}
}
return Dinic.MaxFlow();
}
private:
inline void init() {
E = 1;
}
inline int id(int x, int y) {
return (x-1) * (n+1) + y;
}
inline int sqr(int w) {
return w * w;
}
inline void Add_Edge(int u, int v, int f = INF) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}
inline void Floyd() {
for (int k=1;k<=n;k++) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
};


## 【UOJ 77】A+B Problem

### Code

#include<bits/stdc++.h>
using namespace std;

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[N];

char c=getchar(); int f=1,ret=0;
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;
}

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
static int E = 1; vout += f * t;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
int ch[N][2],root[N],cnt,pur,sur,L,R;

void insert(int p, int &w, int l, int r, int f = 0) {
if (w = ++cnt, p) {
ch[w][0] = ch[p][0];
ch[w][1] = ch[p][1];
}
if (l < r) {
int mid = l + r + 1 >> 1;
if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
else insert(ch[p][1], ch[w][1], mid, r, w);
}

inline void insert(int p, int v) {
pur = v; sur = p;
insert(root[p-1], root[p], 1, tot);
}

void modify(int w, int l, int r) {
if (!w) return;
else if (L <= l && r <= R) Add_Edge(w, pur);
else {
int mid = l + r + 1 >> 1;
if (L < mid) modify(ch[w][0], l, mid-1);
if (mid <= R) modify(ch[w][1], mid, r);
}
}

inline void modify(int p, int node, int l, int r) {
pur = node; L = l; R = r;
modify(root[p], 1, tot);
}
};

int main() {
n = read(); PST::cnt = n << 1;
S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
}
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) {
A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
}
for (int i=1,l,r;i<=n;i++) {
PST::insert(i, A[i]);
PST::modify(i-1, i+n, LL[i], RR[i]);
}
printf("%d\n",vout-Dinic.MaxFlow());
return 0;
}


## 【BZOJ 1497】[NOI2006] 最大获利

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 55000+9;
const int M = N + 100000 << 1;
const int INF = 1e9;

char c=getchar(); int f=1,ret=0;
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;
}

inline void Add_Edge(int u, int v, int f = INF) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

int main() {
S = 0; T = N - 1;
for (int i=1;i<=n;i++)
for (int i=1,t;i<=m;i++) {
}
printf("%d\n",vout-Dinic.MaxFlow());
return 0;
}


#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000 + 9;
const int M = 100000 << 1;
const int INF = 1e9;

char c=getchar(); int f=1,ret=0;
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;
}

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = f * t;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

int main() {
S = 0; T = N - 1;
for (int i=1;i<=n;i++)
for (int i=1,t,x,y;i<=m;i++) {
vout += (t = read()) * 2;
tmp[x] += t; tmp[y] += t;
}
for (int i=1;i<=n;i++)
printf("%d\n",vout-Dinic.MaxFlow()>>1);
return 0;
}


## 【BZOJ 3345】[Pku2914] Minimum Cut

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;

int n,m,vout=INF,cnt,id[N],dis[N],pur,T=1;
queue<int> que;

inline void Add_Edge(int u, int v, int w) {
to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}

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;
}

inline bool BFS(int s, int t) {
memset(dis,-1,sizeof(dis));
que.push(s); dis[s] = 0;

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 == pur) 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]));
flow[i] -= tmp; flow[i^1] += tmp;
ret += tmp; f -= tmp; if (!f) return ret;
}
return ret;
}
}

inline int Dinic(int s, int t){
int ret = 0; pur = t;
while (BFS(s,t)) {
ret += DFS(s,INF);
} return ret;
}

void SIGN(int w) {
dis[w] = 1;
if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}

void solve(int l , int r){
if (l >= r) return ;
static int tmp[N]; int L=l-1, R=r+1;

for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
vout = min(vout, Dinic(id[l],id[r]));

memset(dis,-1,sizeof(dis)); SIGN(id[l]);
for (int i=l;i<=r;i++)
if (~dis[id[i]]) tmp[++L] = id[i];
else tmp[--R] = id[i];
for (int i=l;i<=r;i++) id[i] = tmp[i];
solve(l,L); solve(R,r);
}

int main(){
for (int i=1;i<=n;i++) id[i] = i; solve(1,n);
printf("%d\n",vout);
return 0;
}


## 【算法笔记】网络流相关·第二波冲刺

1）最小路径覆盖（路径问题）：出度入度拆点后跑二分图匹配
2）最大独立集：二分图建图后跑最小割
3）供求关系可以考虑二分图
4）棋盘类问题可以考虑染色
5）最大权闭合子图
6）列出数学等式，按等式的正负配合流量平衡进行建图

## 【BZOJ 1391】[Ceoi2008] order

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const int M = 4000000;
const int INF = 1000000000;

queue<int> que;

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;
}

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()) {
ret += DFS(S,INF);
} return ret;
}

int main(){
n = read(); m = read(); S = 0; T = N-1;
for (int i=1,t1,t2,t3;i<=n;i++) {
}
printf("%d\n",vout-Dinic());
return 0;
}


## 【BZOJ 3275】Number

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;

queue<int> que;

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()) {
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) 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

—– UPD 2016.9.18 —–

## 【BZOJ 2127】happiness

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 100+9;
const int N = 10000+9;
const int M = 500000+9;
const int INF = 100000000;

int dis[N],cur[N],S,T; queue<int> que;

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 id(i,j) ((i)+((j)-1)*n)
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] = f;
}

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()) {
ret += DFS(S,INF);
} return ret;
}

int main(){
m = read(); n = read(); S = 0; T = N-1;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), wen[i][j] += tmp*2;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), li[i][j] += tmp*2;
for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), wen[i][j] += tmp, wen[i+1][j] += tmp;
for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), li[i][j] += tmp, li[i+1][j] += tmp;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), wen[i][j] += tmp, wen[i][j+1] += tmp;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), li[i][j] += tmp, li[i][j+1] += tmp;
printf("%d\n",vout-Dinic()/2);
return 0;
}


## 【BZOJ 2132】圈地计划

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 100+9;
const int N = L*L+9;
const int M = N*15;
const int INF = 1000000000;

int S,T,dis[N],cur[N]; queue<int> que;

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 id(i,j) (i+((j)-1)*n)
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] = f;
}

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()) {
ret += DFS(S,INF);
} return ret;
}

int main(){
m = read(); n = read(); S = 0; T = N-1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (A[i][j] = read());
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (B[i][j] = read());
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) C[i][j] = read();
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
if (j > 1 && i+j&1) Add_Edge(id(i,j),id(i,j-1),C[i][j]+C[i][j-1]), vout += C[i][j]+C[i][j-1];
if (i > 1 && i+j&1) Add_Edge(id(i,j),id(i-1,j),C[i][j]+C[i-1][j]), vout += C[i][j]+C[i-1][j];
if (j < m && i+j&1) Add_Edge(id(i,j),id(i,j+1),C[i][j]+C[i][j+1]), vout += C[i][j]+C[i][j+1];
if (i < n && i+j&1) Add_Edge(id(i,j),id(i+1,j),C[i][j]+C[i+1][j]), vout += C[i][j]+C[i+1][j];
} printf("%d\n",vout-Dinic());
return 0;
}


## 【BZOJ 2768】[JLOI2010] 冠军调查

BZOJ_1934

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300+9;
const int M = N*N*2;
const int INF = 10000000;

queue<int> que;

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;
}

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] = f;
}

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()) {