安徽省建设质量安全协会网站,手机微信一体网站建设,wordpress 更换网址,班级网站素材下载正题
P2805 题目大意
在一个nmn\times mnm的平面上有若干植物#xff0c;每个植物有其攻击集合#xff0c;吃掉一个植物要先吃掉该植物右边的所有植物#xff0c;且该植物不能在任何一个植物的攻击集合内#xff0c;吃掉后有贡献ai,ja_{i,j}ai,j#xff0c;问你最大贡…正题
P2805 题目大意
在一个n×mn\times mn×m的平面上有若干植物每个植物有其攻击集合吃掉一个植物要先吃掉该植物右边的所有植物且该植物不能在任何一个植物的攻击集合内吃掉后有贡献ai,ja_{i,j}ai,j问你最大贡献 解题思路
先按植物先后吃的顺序连边然后跑拓扑序判断哪些植物能吃
然后直接对能吃的植物跑最大权闭合子图 code
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 610
using namespace std;
int n,m,x,y,g,s,t,nm,ans,tot,tott,v[N],h[N],hd[N],dep[N],deg[N];
queueintd;
struct rec
{int to,nx,edge;
}e[N*N1];
struct recc
{int to,nx;
}a[N*N];
const int inf1e8;
int get(int x,int y)
{return x*my;
}
void add(int x,int y)
{a[tott].toy;a[tott].nxhd[x];hd[x]tott;deg[y];return;
}
void addl(int x,int y,int z)
{e[tot].toy;e[tot].edgez;e[tot].nxh[x];h[x]tot;e[tot].tox;e[tot].edge0;e[tot].nxh[y];h[y]tot;return;
}
void prebfs()
{for(int i0;inm;i)if(!deg[i]){d.push(i);if(v[i]0){ansv[i];addl(s,i,v[i]);}else if(v[i]0)addl(i,t,-v[i]);}while(!d.empty()){int xd.front();d.pop();for(int ihd[x];i;ia[i].nx){int ya[i].to;deg[y]--;if(!deg[y]){d.push(y);if(v[y]0){ansv[y];addl(s,y,v[y]);}else if(v[y]0)addl(y,t,-v[y]);}}}return;
}
bool bfs()
{memset(dep,0,sizeof(dep));dep[s]1;while(!d.empty())d.pop();d.push(s);while(!d.empty()){int xd.front();d.pop();for(int ih[x];i;ie[i].nx){int ye[i].to;if(dep[y]||!e[i].edge)continue;dep[y]dep[x]1;if(yt)return true;d.push(y);}}return false;
}
int dfs(int x,int flow)
{if(xt)return flow;int rest0,k;for(int ih[x];i;ie[i].nx){int ye[i].to;if(dep[y]!dep[x]1||!e[i].edge)continue;kdfs(y,min(e[i].edge,flow-rest));if(!k)dep[y]0;restk;e[i].edge-k;e[i^1].edgek;if(flowrest)return rest;}return rest;
}
int main()
{scanf(%d%d,n,m);nmget(n-1,m-1);snm1;tnm2;tot1;for(int i0;in;i)for(int j0;jm;j){scanf(%d,v[get(i,j)]);scanf(%d,g);for(int k1;kg;k){scanf(%d%d,x,y);add(get(i,j),get(x,y));addl(get(x,y),get(i,j),inf);}if(j){add(get(i,j),get(i,j-1));addl(get(i,j-1),get(i,j),inf);}}prebfs();while(bfs())ans-dfs(s,inf);printf(%d,ans);return 0;
}
