喜羊羊与灰太狼

网络流之最小割

哎，傻逼题，建图跑一次最小割 完事
狼与空地和🐏连上
空地连空地 和🐏
🐏与🐺分别连汇点与源点 inf边容 不会被割掉

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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 int
using 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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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 int
using 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);
}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！