## 【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 1066】[SCOI2007] 蜥蜴

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

const int L = 25;
const int N = L*L*2+9;
const int M = N*100;
const int INF = 10000000;

int m,n,d,mat[L][L],vout,S,T;
char pat[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(x,y,ty) ((x)+((y)-1)*n+(ty)*m*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(){
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++) mat[i][j] = pat[i] - '0';
for (int i=1;i<=n;i++) if (mat[i][j]) Add_Edge(id(i,j,0),id(i,j,1),mat[i][j]);
}
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++) if (pat[i] == 'L') Add_Edge(S,id(i,j,0),1), vout++;
}
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (mat[i][j]) {
for (int x=1;x<=n;x++) for (int y=1;y<=m;y++)
if (mat[x][y] && abs(x-i)+abs(y-j) <= d) Add_Edge(id(i,j,1),id(x,y,0),INF);
}
vout -= Dinic();
printf("%d\n",vout);
return 0;
}


## 【BZOJ 4625】[BeiJing2016] 水晶

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

const int N = 500000+9;
const int M = 1000000+9;
const int SGZ = 4100+9;
const int INF = 100000000;

int n,mat[SGZ][SGZ],idx[SGZ][SGZ],S,T,vout;
struct Point{int x,y,t,c;}p[N];
queue<int> que;

inline bool cmp(const Point &A, const Point &B) {return A.x == B.x && A.y == B.y;}
inline bool CMP(const Point &A, const Point &B) {return A.x < B.x || (A.x == B.x && A.y < B.y);}

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

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

inline void Add_Edge(int u, int v, int f){
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;
}

int main(){
for (int i=1,x,y,z,c;i<=n;i++) {
x += 2001 - z; y += 2001 - z; p[i].t = (x+y) % 3;
c *= ((x+y)%3)?10:11;	mat[x][y] += c; vout += c;
p[i].x = x; p[i].y = y;
}
sort(p+1,p+1+n,CMP);
n = unique(p+1,p+1+n,cmp) - p - 1;
S = n*2 + 1, T = n*2 + 2;
for (int i=1;i<=n;i++) idx[p[i].x][p[i].y] = i, p[i].c = mat[p[i].x][p[i].y];
for (int i=1;i<=n;i++)
else if (p[i].t == 2) Add_Edge(i,T,p[i].c);
for (int i=1,x,y;i<=n;i++) if (!p[i].t) {
x = p[i].x; y = p[i].y;
}
vout -= Dinic();
cout<<vout/10<<'.'<<vout%10;
return 0;
}


—– UPD 2016.9.10 —–
YYY告诉我，这货不是很常见的构图？

—– UPD 2016.9.13 —–

http://acm.hit.edu.cn/hoj/problem/view?id=2713