【网络流】- LA5905-Pool construction

本文主要是介绍【网络流】- LA5905-Pool construction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：我是链接啊啊啊哈哈哈

题意：

嘛。。也许见多了就会建图了。。学习着吧

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 3000;
const int maxm = 60000;
const int INF = 0x7FFFFFF;
#define mem(name,value) memset((name),(value),sizeof(name))
struct Side{int to,next,c;
}side[maxm];
int top,node[maxn];
void add_side(int u,int v,int c,int rc){//cout<<u<<" --> "<<v<<" need "<<c<<endl;side[top]=(Side){v,node[u],c};node[u]=top++;side[top]=(Side){u,node[v],rc};node[v]=top++;
}
int start,end,cnt,dis[maxn],gap[maxn];
int get_flow(int u,int flow){//printf("%d %d\n",u,flow);if(u==end)return flow;int ans=0;for(int i=node[u];i!=-1;i=side[i].next){int v=side[i].to,c=side[i].c;if(dis[u]>dis[v]&&c){int f=get_flow(v,min(flow-ans,c));ans+=f;side[i].c-=f;side[i^1].c+=f;if(ans==flow)return ans;}}if(!(--gap[dis[u]]))dis[start]=cnt+2;gap[++dis[u]]++;return ans;
}char grid[55][55];
int fans,f,d,b,cnn;
int n,m;int getid(int x,int y)
{return x*n+y+1;
}void deal_ini()
{//cout<<"****"<<endl;int i,j;int id;//cout<<"n="<<n<<endl;for(i=0;i<n;i++){//cout<<"****"<<endl;if(grid[0][i] == '.') fans += f;id = getid(0,i);//cout<<0<<" --> "<<id<<" need "<<INF<<endl;add_side(0,id,INF,0);if(grid[m-1][i] == '.') fans += f;id = getid(m-1,i);add_side(0,id,INF,0);}for(i=1;i<m-1;i++){if(grid[i][0] == '.') fans += f;id = getid(i,0);add_side(0,id,INF,0);if(grid[i][n-1] == '.') fans += f;id = getid(i,n-1);add_side(0,id,INF,0);}
}void makemap()
{int i,j,id;for(i=1;i<m-1;i++){for(j=1;j<n-1;j++){id = getid(i,j);if(grid[i][j] == '#')add_side(0,id,d,0);elseadd_side(id,m*n+1,f,0);}}for(i=1;i<m;i++){for(j=0;j<n;j++){int id1 = getid(i,j);int id2 = getid(i-1,j);add_side(id1,id2,b,0);add_side(id2,id1,b,0);}}for(j=1;j<n;j++){for(i=0;i<m;i++){int id1 = getid(i,j);int id2 = getid(i,j-1);add_side(id1,id2,b,0);add_side(id2,id1,b,0);}}
}int main(){//freopen("input.txt","r",stdin);int T;scanf("%d",&T);while(T--){fans=0;cnn=1;memset(grid,0,sizeof(grid));scanf("%d%d",&n,&m);scanf("%d%d%d",&d,&f,&b);for(int i=0;i<m;i++)scanf("%s",grid[i]);/*for(int i=0;i<m;i++)cout<<grid[i]<<endl;*/top=0;mem(node,-1);mem(gap,0);mem(dis,0);deal_ini();makemap();int ans=0;start=0;end=n*m+1;cnt=n*m+2;gap[0]=cnt;while(dis[start]<cnt)ans+=get_flow(start,INF);printf("%d\n",ans+fans);}return 0;
}

这篇关于【网络流】- LA5905-Pool construction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---