## 【日常小测】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;
}


## 【BZOJ 2438】[中山市选2011] 杀人游戏

PS:此题的随机数据不容易拍出错QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

const int MAXN = 300000+9;

int scc_num[MAXN],scc_sz[MAXN],scc_cnt;
stack<int> sta;

inline void AddEdge(int u, int v){
static int T = 0;
}

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

void DFS(int w) {
static int tot = 0; sta.push(w);
}
scc_cnt += 1;
while (true) {
int nw = sta.top(); sta.pop();
scc_num[nw] = scc_cnt;
scc_sz[scc_cnt]++;
if (nw == w) break;
}
}
}

int main(){
for (int i=1;i<=n;i++) if (!num[i]) DFS(i);
for (int i=1;i<=n;i++) for (int j=head[i];j;j=nxt[j])
if (scc_num[to[j]] != scc_num[i]) in[scc_num[to[j]]]++;
for (int i=1;i<=scc_cnt;i++) if (!in[i]) vout++;
for (int i=1,tag=0;i<=n;i++,tag=0) if (scc_sz[scc_num[i]] == 1 && !in[scc_num[i]]) {
for (int j=head[i];j;j=nxt[j]) if (in[scc_num[to[j]]] == 1 && scc_num[to[j]] != scc_num[i]) {tag = 1; break;}
if (!tag) {vout--; break;}
}
printf("%.6lf\n",1.0-(double)vout/n);
return 0;
}