网络流之最小割
哎，傻逼题，建图跑一次最小割 完事
狼与空地和🐏连上
空地连空地 和🐏
🐏与🐺分别连汇点与源点 inf边容 不会被割掉
#include <bits/stdc++.h>#include <stdlib.h>#include <algorithm>#include <stdio.h>#include <string.h>#include <queue>#include <time.h>#include <cstdio>#include <iostream>#include <vector>#define ll int//#define int long long#define inf 0x3f3f3f#define mods 1000000007#define modd 998244353#define PI acos(-1)#define fi first#define se second#define lowbit(x) (x & (-x))#define mp make_pair#define pb push_back#define si size()#define E exp(1.0)#define fixed cout.setf(ios::fixed)#define fixeds(x) setprecision(x)#define Re register intusing namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}const int N = 3*1e5, M = 5 * 1e6 + 3;int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N],zhanv;ll maxflow;struct QAQ {int to, next, flow;} a[M << 1];ll yy=0;ll la=0;inline void in(Re &x) {int f = 0;x = 0;char c = getchar();while (c < '0' || c > '9') f |= c == '-', c = getchar();while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();x = f ? -x : x;}inline void add(Re x, Re y, Re z) {a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }inline int bfs(Re st, Re ed) {// bfs求源点到所有点的最短路for (Re i = 0; i <= n*m+1; ++i) cur[i] = head[i], dis[i] = 0; //当前弧优化cur=headh = 1, t = 0, dis[st] = 1, Q[++t] = st;while (h <= t) {Re x = Q[h++], to;for (Re i = head[x]; i; i = a[i].next)if (a[i].flow && !dis[to = a[i].to]) {dis[to] = dis[x] + 1, Q[++t] = to;if (to == ed)return 1;}}return 0;}inline int dfs(Re x, Re flow) {// flow为剩下可用的流量if (!flow || x == ed)return flow; //发现没有流了或者到达终点即可返回Re tmp = 0, to, f;for (Re i = cur[x]; i; i = a[i].next) {cur[x] = i; //当前弧优化cur=iif (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {//若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了a[i].flow -= f, a[i ^ 1].flow += f;tmp += f; //记录终点已经从x这里获得了多少流if (!(flow - tmp))break;// 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。//而此时边i很可能还没有被榨干，所以cur[x]即为i。// 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。//于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'//直至榨干从x上面送下来的水流结束（即情况1）。}}return tmp;}inline void Dinic(Re st, Re ed) {Re flow = 0;while (bfs(st, ed)) maxflow += dfs(st, inf);}ll as[300][300];struct pe{ll x,y;}wolf[50090];struct pp{ll x,y;}she[50090];void cle(){maxflow=0;o=1;memset(head,0,sizeof(head));la=0;yy=0;}signed main(){ll ca=0;while(scanf("%d %d",&n,&m)!=EOF){if(n<=0&&m<=0){break;}ca++;cle();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){read(as[i][j]);if(as[i][j]==1){++yy;she[yy].x=i;she[yy].y=j;}if(as[i][j]==2){++la;wolf[la].x=i;wolf[la].y=j;}}}for(int i=1;i<=la;i++){ll ok=(wolf[i].x-1)*m+wolf[i].y; //x y转为节点号ll zyx;add(0,ok,inf); //鸽不掉add(ok,0,0);if(wolf[i].x>1&&as[wolf[i].x-1][wolf[i].y]!=2){//向上zyx=(wolf[i].x-2)*m+wolf[i].y;add(ok,zyx,1);add(zyx,ok,0);}if(wolf[i].x<n&&as[wolf[i].x+1][wolf[i].y]!=2){//向下zyx=(wolf[i].x)*m+wolf[i].y;add(ok,zyx,1);add(zyx,ok,0);}if(wolf[i].y>1&&as[wolf[i].x][wolf[i].y-1]!=2){//向左zyx=(wolf[i].x-1)*m+wolf[i].y-1;add(ok,zyx,1);add(zyx,ok,0);}if(wolf[i].y<m&&as[wolf[i].x][wolf[i].y+1]!=2){//向右zyx=(wolf[i].x-1)*m+wolf[i].y+1;add(ok,zyx,1);add(zyx,ok,0);}}for(int i=1;i<=yy;i++){ll ok=(she[i].x-1)*m+she[i].y; //x y转为节点号ll zyx;add(ok,n*m+1,inf);add(n*m+1,ok,0);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(as[i][j]==0){ll ok=(i-1)*m+j;ll zyx;if(i>1&&as[i-1][j]!=2){zyx=(i-2)*m+j;add(ok,zyx,1);add(zyx,ok,0);}if(i<n&&as[i+1][j]!=2){zyx=(i)*m+j;add(ok,zyx,1);add(zyx,ok,0);}if(j>1&&as[i][j-1]!=2){zyx=(i-1)*m+j-1;add(ok,zyx,1);add(zyx,ok,0);}if(j<m&&as[i][j+1]!=2){zyx=(i-1)*m+j+1;add(ok,zyx,1);add(zyx,ok,0);}}}}st=0;ed=n*m+1;Dinic(st,ed);printf("Case %d:\n",ca);printf("%d\n",maxflow);}return 0;}
二分图匹配&&联通块
自我感觉是跟 黑白棋 如出一辙的题 标记好联通块了再求一次最小点覆盖
#include <bits/stdc++.h>#include <stdlib.h>#include <algorithm>#include <stdio.h>#include <string.h>#include <queue>#include <time.h>#include <cstdio>#include <iostream>#include <vector>#define ll long long#define int long long#define inf 0x3f3f3f3f#define mods 1000000007#define modd 998244353#define PI acos(-1)#define fi first#define se second#define lowbit(x) (x & (-x))#define mp make_pair#define pb push_back#define si size()#define E exp(1.0)#define fixed cout.setf(ios::fixed)#define fixeds(x) setprecision(x)#define Re register intusing namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}ll hh=0;ll ss=0;const int N = 1e5 + 3, M = 5 * 1e6 + 3;int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N],zhanv;long long maxflow;struct QAQ {int to, next, flow;} a[M << 1];inline void in(Re &x) {int f = 0;x = 0;char c = getchar();while (c < '0' || c > '9') f |= c == '-', c = getchar();while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();x = f ? -x : x;}inline void add(Re x, Re y, Re z) {a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }inline int bfs(Re st, Re ed) {// bfs求源点到所有点的最短路for (Re i = 0; i <= hh+ss+1; ++i) cur[i] = head[i], dis[i] = 0; //当前弧优化cur=headh = 1, t = 0, dis[st] = 1, Q[++t] = st;while (h <= t) {Re x = Q[h++], to;for (Re i = head[x]; i; i = a[i].next)if (a[i].flow && !dis[to = a[i].to]) {dis[to] = dis[x] + 1, Q[++t] = to;if (to == ed)return 1;}}return 0;}inline int dfs(Re x, Re flow) {// flow为剩下可用的流量if (!flow || x == ed)return flow; //发现没有流了或者到达终点即可返回Re tmp = 0, to, f;for (Re i = cur[x]; i; i = a[i].next) {cur[x] = i; //当前弧优化cur=iif (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {//若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了a[i].flow -= f, a[i ^ 1].flow += f;tmp += f; //记录终点已经从x这里获得了多少流if (!(flow - tmp))break;// 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。//而此时边i很可能还没有被榨干，所以cur[x]即为i。// 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。//于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'//直至榨干从x上面送下来的水流结束（即情况1）。}}return tmp;}inline void Dinic(Re st, Re ed) {Re flow = 0;while (bfs(st, ed)) maxflow += dfs(st, inf);}char str[80][90];ll hx[80][80];ll sy[80][80];void cle(){memset(hx,0,sizeof(hx));memset(sy,0,sizeof(sy));hh=0;ss=0;o=1;maxflow=0;memset(head,0,sizeof(head));}signed main(){while(scanf("%lld%lld",&n,&m)!=EOF){if(n<=0||m<=0){break;}cle();for(int i=1;i<=n;i++){scanf("%s",str[i]+1);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(str[i][j]=='*'){if(j==1||str[i][j-1]=='.'){hx[i][j]=++hh;}else{hx[i][j]=hh;}}}}for(int j=1;j<=m;j++){for(int i=1;i<=n;i++){if(str[i][j]=='*'){if(i==1||str[i-1][j]=='.'){sy[i][j]=(++ss)+hh;}else{sy[i][j]=ss+hh;}}}}for(int i=1;i<=hh;i++){add(0,i,1);add(i,0,0);}for(int i=1;i<=ss;i++){add(i+hh,hh+ss+1,1);add(hh+ss+1,i+hh,0);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(str[i][j]!='.'){add(hx[i][j],sy[i][j],1);add(sy[i][j],hx[i][j],0);}}}st=0;ed=hh+ss+1;Dinic(st,ed);printf("%lld\n",maxflow);}}
