## 【日常小测】仰望星空

### Code

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

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
int x, y, ty;
inline int dis(const Point &P) {
return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
}
}p[N];

inline void AddEdge(int u, int v) {
static int E = 1;
}

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline bool DFS(int w) {
vis[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
mth[to[i]] = w;
mth[w] = to[i];
return 1;
}
}
return 0;
}

inline int solve() {
int ret = 0;
for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
if (!mth[i]) {
memset(vis, 0, sizeof(vis));
ret += DFS(i);
}
}
return ret;
}

inline void print(int w) {
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] == mth[w]) {
vis[w] = vis[to[i]] = 1;
printf("%d %d\n", w, mth[w]);
return;
} else if (!vis[to[i]]){
print(mth[to[i]]);
}
}
}

int main() {
R = read(); R *= R;
D = read(); D *= D;
S = 0; T = N - 1;
for (int i = 1; i <= n; i++) {
if (p[i].ty = p[i].dis(p[1]) > R) {
in[++cnt_in] = i;
} else {
ot[++cnt_ot] = i;
}
}
for (int ii = 1; ii <= cnt_in; ii++) {
int i = in[ii], cnt_arr = 0;
double mx = -PI, mn = PI;
for (int jj = 1; jj <= cnt_ot; jj++) {
int j = ot[jj];
if (p[i].dis(p[j]) <= D) {
double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
mx = max(mx, agl);
mn = min(mn, agl);
arr[++cnt_arr] = make_pair(agl, j);
}
}
if (mx - mn >= PI) {
for (int j = 1; j <= cnt_arr; j++) {
arr[j].first += arr[j].first < 0? PI * 2: 0;
}
}
sort(arr + 1, arr + 1 + cnt_arr);
for (int j = 1; j <= cnt_arr; j++) {
}
}
printf("%d\n", solve() << 1);
memset(vis, 0, sizeof(vis));
for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
if (mth[i] && !vis[i]) {
print(i);
}
}
return 0;
}


## 【BZOJ 1937】[SHOI2004] Mst最小生成树

### 解题报告

←为什么这个频率这个鬼畜啊 QwQ

## 【日常小测】Mortal Kombat

### Code

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

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

int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N];
stack<int> stk;

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 int AddEdge(int u, int v, int f=0) {
if (f) {
flow[E - 1] = f; return E - 1;
}

class Network_Flow{
int dis[N],cur[N]; queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
} return ret;
}
private:
int DFS(int w, int f) {
if (w == T) return f; int ret = 0;
for (int &i=cur[w],tmp;i;i=nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) return ret;
}
} return ret;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
} return dis[T] < INF;
}
}Dinic;

void Tarjan(int w) {
static int dfs_cnt = 0, scc_cnt = 0;
dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);
}
if (low[w] == dfs[w]) {
for (scc_cnt++;!stk.empty();stk.pop()) {
num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
if (stk.top() == w) {stk.pop(); break;}
}
}
}

int main() {
n = read(); m = read(); S = 0; T = N - 1;
memset(id, -1, sizeof(id));
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
for (int j=1;j<=m;j++) {
if (pat[j] == '1') {
id[i][j] = AddEdge(i, m + j, 1);
}
}
}
for (int i=1;i<=n;i++) AddEdge(S, i, 1);
for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
if (Dinic.MaxFlow() != n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) putchar('1');
puts("");
}
} else {
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
else putchar('1');
} putchar('\n');
}
}
return 0;
}


## 【TopCoder SRM570】Curvy on Rails

### 解题报告

1. 回路中的每一个点的度一定是 $2$
2. 如果每一个点的度都是 $2$ ，那么这一定是由一些回路构成的图

1. 横向的度
2. 纵向的度

### Code

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

const int L = 30;
const int N = 2000;
const int M = 50000;
const int INF = 1000000000;

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

class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline pair<int,int> MaxFlow() {
int ret_cost = 0, ret_flow = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
ret_flow += f;
}
return make_pair(ret_cost, ret_flow);
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;

class CurvyonRails {
int n,m,cnt,E;
char pat[L][L];
public:
int getmin(vector<string> field) {
init();
m = field.size();
n = field[0].size();
for (int j=0;j<m;j++) {
for (int i=0;i<n;i++) {
pat[i+1][j+1] = field[j][i];
}
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (pat[i][j] == 'w') continue;
else {
if (++cnt, i + j & 1) {
} else {
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) {
if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1);
if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1);
}
}
}
if (pat[i][j] == '.') {
}
if (pat[i][j] == 'C') {
}
}
}
}
pair<int,int> vout = MCMF.MaxFlow();
if (vout.second < cnt) return -1;
else return vout.first;
}
private:
inline int id(int x, int y, int t) {
return ((y-1)*n + (x-1)) * 2 + 1 + t;
}
inline void init() {
E = 1; S = cnt = 0; T = N - 1;
}
inline void Add_Edge(int u, int v, int f, int c = 0) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}
};


## 【TopCoder SRM578】DeerInZooDivOne

### Code

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

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

int n,m,S,T;

class Minimum_Cost_Flow{
int E,vout,dis[N],sur[N],inq[N];
queue<int> que;
public:
inline void init() {
E = 1; S = 0; T = N - 1;
}
inline void Add_Edge(int u, int v, int f, int c) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}
inline int MaxFlow() {
vout = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
vout += dis[T] * f;
}
return vout;
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;

class DeerInZooDivOne {
int ret,t1,t2,q1[N],q2[N],fa[N],f[N][N];
public:
int getmax(vector<int> a, vector<int> b) {
n = a.size(); init();
for (int i=0;i<n;i++)
for (int i=0;t1=t2=0,i<n;i++) {
DFS(a[i]+1, b[i]+1, q1, t1);
DFS(b[i]+1, a[i]+1, q2, t2);
vis[i*2+1] = vis[(i+1)*2] = 1;
for (int p1=1;p1<=t1;p1++) {
Make_Root(q1[p1], q1[p1]);
for (int p2=1;p2<=t2;p2++) {
Make_Root(q2[p2], q2[p2]);
memset(f,-1,sizeof(f));
ret = max(ret, F(q1[p1], q2[p2]));
}
}
vis[i*2+1] = vis[(i+1)*2] = 0;
}
return ret;
}
private:
inline void init() {
E = 0; ret = 1;
}
inline void Add_Edge(int u, int v) {
}
void DFS(int w, int f, int *arr, int &cnt) {
arr[++cnt] = w;
if (to[i] != f) {
DFS(to[i], w, arr, cnt);
}
}
}
void Make_Root(int w, int f) {
fa[w] = f;
if (to[i] != f && !vis[i]) {
Make_Root(to[i], w);
}
}
}
inline int F(int a, int b) {
if (a > b) swap(a, b);
if (~f[a][b]) return f[a][b];
else {
if (to[i] != fa[a] && !vis[i]) {
if (to[j] != fa[b] && !vis[j]) {
F(to[i], to[j]);
}
}
}
}
MCMF.init();
if (to[i] != fa[a] && !vis[i]) {
if (to[j] != fa[b] && !vis[j]) {
}
}
}
}
if (to[i] != fa[b] && !vis[i]) {
}
}
f[a][b] = -MCMF.MaxFlow();
return ++f[a][b];
}
}
};


## 【BZOJ 4443】[Scoi2015] 小凸玩矩阵

### Code

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

const int N = 500 + 9;
const int M = 500000;
const int INF = 1e9;

int n,m,K,S,T,val[N/2][N/2],tot,TMP[M];
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) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > dis[w] + 1 && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}

return dis[T] < 1e8;
}

int DFS(int w, int v) {
if (w == T) {
return v;
} else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
int tmp = DFS(to[i], min(v, flow[i]));
v -= tmp; ret += tmp;
flow[i] -= tmp; flow[i^1] += tmp;
if (!v) break;
}
}
return ret;
}
}

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

inline bool judge(int sta) {
TT = 1; S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (val[i][j] <= sta) {
}
}
}
for (int i=1;i<=m;i++)
return Dinic() >= n - K + 1;
}

int main(){
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
}
}
sort(TMP+1, TMP+1+tot);
tot = unique(TMP+1, TMP+1+tot) - TMP - 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
val[i][j] = lower_bound(TMP+1, TMP+1+tot, val[i][j]) - TMP;
}
}

int l=1, r=tot, mid, vout=0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) r = mid-1, vout = mid;
else l = mid + 1;
}
printf("%d\n",TMP[vout]);
return 0;
}


## 【BZOJ 4514】[Sdoi2016] 数字配对

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

const int M = 200+9;
const int N = 100000+9;
const int MX = 100000;
const int INF = 0x7fffffff;

int pri[N],tot,vis[N],n,A[M],B[M],C[M];
int lft[M],rit[M],tl,tr,sur[M],S,T,inq[M];
LL cost[N],dis[M];
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 Get_Prime_Number(){
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++tot] = i;
for (int j=1;j<=tot&&i*pri[j]<=MX;j++)
if (i%pri[j]) vis[i*pri[j]] = 1;
else {vis[i*pri[j]] = 1; break;}
}
}

inline void Add_Edge(int u, int v, int f, LL c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline bool divide(int w) {int ret = 0; for (int i=1;i<=tot;i++) while (w%pri[i] == 0) w /= pri[i], ret++; return ret&1;}
inline bool is_prime(int w) {for (int i=1;i<=tot;i++) if (pri[i] >= w) break; else if (w%pri[i] == 0) return false; return true;}

inline bool SPFA(){
memset(dis,127,sizeof(dis));
que.push(S); inq[S] = 1; dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
} return dis[T] < dis[M-2];
}

inline LL MCMF(){
LL ret = 0, tot_cost = 0; bool tag=1;
for (int w=T,f;SPFA()&&tag;w=T) {
for (f=INF;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
if (dis[T]*f+tot_cost > 0) ret += -tot_cost / dis[T], tag = 0;
else {
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret += f; tot_cost += f*dis[T];
}
} return ret;
}

int main(){
n = read(); Get_Prime_Number(); S = 0; T = M - 1;
for (int i=1;i<=n;i++) A[i] = read();
for (int i=1;i<=n;i++) B[i] = read();
for (int i=1;i<=n;i++) C[i] = read();
for (int i=1;i<=n;i++)
if (divide(A[i])) lft[++tl] = i, Add_Edge(S,i,B[i],0);
for (int i=1;i<=tl;i++) for (int j=1;j<=tr;j++) {
int w1 = A[lft[i]], w2 = A[rit[j]]; if (w1 > w2) swap(w1, w2);
if (w2 % w1 == 0 && is_prime(w2 / w1))
} printf("%lld\n",MCMF());
return 0;
}


## 【BZOJ 1458】士兵占领

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

const int L = 100+9;
const int N = 50000+9;
const int M = 1000000;
const int INF = 1000000000;

int n,m,X[L],Y[L],cx[L],cy[L],k,S,T,mat[L][L],vout;
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(x,y) (x+(y-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] = 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(){
m = read(); n = read(); k = read(); S = 0, T = N-1; vout = n*m;
for (int i=1;i<=m;i++) Y[i] = read(), cy[i] = n;
for (int i=1;i<=n;i++) X[i] = read(), cx[i] = m;
for (int i=1,x,y;i<=k;i++) x = read(), y = read(), mat[x][y] = 1, cx[x]--, cy[y]--, vout--;
for (int i=1;i<=m;i++) if (cy[i] < Y[i]) puts("JIONG!"), exit(0);
for (int i=1;i<=n;i++) if (cx[i] < X[i]) puts("JIONG!"), exit(0);

for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (!mat[i][j])
printf("%d\n",vout-Dinic());
return 0;
}


## 【BZOJ 1711】[Usaco2007 Open] Dining吃饭

《网络流建模汇总》的例题

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

const int N = 400+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;
}

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(){
for (int i=1,t1,t2;i<=n;i++) {
} printf("%d\n",Dinic());
return 0;
}


## 【BZOJ 1433】[ZJOI2009] 假期的宿舍

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

const int N = 10000;
const int M = 100000;
const int INF = 100000000;

int n,vout,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;
}

inline void Add_Edge(int u, int v, int f) {
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(){
int TTT; cin>>TTT; while (TTT--) {
memset(in_school,0,sizeof(in_school));
memset(live_school,0,sizeof(live_school));
n = read(); vout = 0; TT = 1; S = 0; T = N-1;
for (int i=1;i<=n;i++) if (in_school[i] || !live_school[i]) Add_Edge(S,i,1), vout++;
if(Dinic() == vout)puts("^_^");
else puts("T_T");
}
return 0;
}


## 【COGS 396】[网络流24题] 魔术球问题（简化版

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

const int N = 100000;
const int INF = 10000000;

int n,m,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(x,ty) ((x)*2+ty)
inline int Add_Edge(int u, int v, int f) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
return TT - 1;
}

inline bool BFS(){
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];
}

inline int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int &i=head[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) break;
} return ret;
}
}

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

int main(){
freopen("balla.in","r",stdin);
freopen("balla.out","w",stdout);
n = read(); S = 0; T = 1;
for (int i=1,w=0;i<=1600;i++) {
for (int j=i-1;j;j--) if (i + j == (int)sqrt(i+j)*(int)sqrt(i+j)) Add_Edge(id(i,0),id(j,1),1);
w += Dinic(); if (i - w > n) cout<<i-1, exit(0);
}
return 0;
}


## 【COGS 728】[网络流24题] 最小路径覆盖问题

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

const int N = 10000;
const int M = 100000;
const int INF = 1000000;

int vout,n,m,S,T,vis[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;
}

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

void print(int w) {
vis[w] = 1; printf("%d ",w);
for (int i=head[w];i;i=nxt[i]) if (!flow[i] && !vis[to[i]])
{print(to[i]>n?to[i]-n:to[i]); break;}
}

int main(){
freopen("path3.in","r",stdin);
freopen("path3.out","w",stdout);
vout = n = read(); m = read(); S = 0; T = N-1; vis[S] = vis[T] = 1;
vout -= Dinic();
for (int i=1,w;i<=n;i++) if (!vis[i])
print(i), putchar('\n');
printf("%d\n",vout);
return 0;
}


## 【UOJ 80】二分图最大权匹配

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 600000;
const int INF = 100000000;

int n1,n2,m,s,t; LL vout;
int dis[MAXN],que[MAXN],fro,bak,inq[MAXN],from[MAXN],scr[MAXN];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

inline void AddEdge(int a, int b, int CAP, int COST){
to[++T] = b; from[T] = a; nxt[T] = head[a]; head[a] = T; cap[T] = CAP; cost[T] = COST;
to[++T] = a; from[T] = b; nxt[T] = head[b]; head[b] = T; cap[T] = 0; cost[T] = -COST;
}

inline bool SPFA(){
memset(dis,60,sizeof(dis));
memset(inq,0,sizeof(inq));
dis[s] = 0; que[fro=bak=1]=s;

while (bak <= fro){
int w = que[bak++]; inq[w] = 0;
if (flow[i] < cap[i] && dis[to[i]] > dis[w]+cost[i]){
dis[to[i]] = dis[w] + cost[i]; scr[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que[++fro] = to[i];
}
}
}

return dis[t] <= 0;
}

inline void MCMF(){
while (SPFA()){
int w = t; while (w != s)
flow[scr[w]] += 1, flow[scr[w]^1] -= 1,
vout += cost[scr[w]], w = from[scr[w]];
}
}

int main(){
s = 0; t = n1+n2+1;
for (int i=1,a,b,c;i<=m;i++)
MCMF();
printf("%lld\n",-vout);
for (int i=1;i<=n1;i++){
vout = 0;
if (flow[j] && to[j] > n1)
{vout = to[j] - n1; break;}
printf("%d ",vout);
}
return 0;
}


## 【UOJ 78】二分图最大匹配

Dinic此题的时间还是不错的，能踩Dinic的，都只有二分图专门的算法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 5000000+9;
const int INF = 10000000;

int n1,n2,m,s,t,vout;
int dis[MAXN],que[MAXN],fro,bak;
int cap[MAXN],flow[MAXN],cur[MAXN];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

inline void AddEdge(int a, int b, int CAP){
to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = CAP;
to[++T] = a; nxt[T] = head[b]; head[b] = T; cap[T] = 0;
}

inline bool BFS(){
memset(dis,-1,sizeof(dis));
que[fro=bak=1] = s; dis[s] = 0;

while (bak <= fro) {
int w = que[bak++];
if (flow[i] < cap[i] && dis[to[i]] == -1)
dis[to[i]] = dis[w] + 1, que[++fro] = to[i];
}

return dis[t] != -1;
}

int MaxFlow(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] < cap[i] && dis[to[i]] == dis[w] + 1){
int tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
flow[i] += tmp; flow[i^1] -= tmp;
ret += tmp; if (ret == f) return ret;
}
}
return ret;
}
}

inline void Dinic(){
while (BFS()){
for (int i=0;i<=t;i++) cur[i] = head[i];
vout += MaxFlow(s, INF);
}
}

int main(){
s = 0; t = n1 + n2 + 1;
for (int i=1,a,b;i<=m;i++)