模板网站建设乐云seo效果好,公司网站开发外包公司,廊坊做网站多少钱,试析媒体网站品牌建设正题
题目链接:https://www.luogu.com.cn/problem/P2805 题目大意 n∗mn*mn∗m的格子#xff0c;攻击这个格子(x,y)(x,y)(x,y)可以获得价值cx,yc_{x,y}cx,y#xff0c;攻击一个格子(x,y)(x,y)(x,y)前要攻击(x,y1)(x,y1)(x,y1)。
对于有的格子(x,y)(x,y)(x,y)会保护些格子…正题
题目链接:https://www.luogu.com.cn/problem/P2805 题目大意
n∗mn*mn∗m的格子攻击这个格子(x,y)(x,y)(x,y)可以获得价值cx,yc_{x,y}cx,y攻击一个格子(x,y)(x,y)(x,y)前要攻击(x,y1)(x,y1)(x,y1)。
对于有的格子(x,y)(x,y)(x,y)会保护些格子攻击一个格子直接必须攻击掉保护它的格子。
求最大价值 解题思路
先用拓扑排序去掉一些无法攻击的格子(相互保护或者被相互保护的格子保护的)。
然后就是最大权闭合图的问题就好了跑网络流 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define p(x,y) ((x-1)*my)
using namespace std;
const int N30*40,inf2e9;
struct node{int to,next,w;
}a[N*N];
int ls[N],dep[N],tot1,n,m,ans,s,e,in[N],edge[N][N],c[N],v[N][N];
queueintq;
void add_edge(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;
}
bool bfs()
{memset(dep,0,sizeof(dep));while(!q.empty())q.pop();q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w) continue;q.push(y);dep[y]dep[x]1;if(ye) return 1;}}return 0;
}
int dinic(int x,int flow){int rest0,k;if(xe) return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1dep[y]a[i].w){rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow) return flow;} }if(!rest) dep[x]0;return rest;
}
void net_flow(){while(bfs())ans-dinic(s,inf);
}
void init(){scanf(%d%d,n,m);sp(n,m)1;es1;for(int i1;in;i)for(int j1;jm;j){int k;scanf(%d%d,c[p(i,j)],k);if(c[p(i,j)]0) edge[s][p(i,j)]c[p(i,j)];if(c[p(i,j)]0) edge[p(i,j)][e]-c[p(i,j)];while(k--){int x,y;scanf(%d%d,x,y);x;y;v[p(i,j)][p(x,y)];edge[p(x,y)][p(i,j)]inf,in[p(x,y)];}if(jm) v[p(i,j1)][p(i,j)],edge[p(i,j)][p(i,j1)]inf,in[p(i,j)];}
}
void top_sort(){for(int i1;is;i)if(!in[i])q.push(i);while(!q.empty()){int xq.front();q.pop();for(int y1;ys;y){if(!v[x][y]) continue;in[y]-v[x][y];if(!in[y])q.push(y);}}
}
void build_graph(){for(int i1;is;i)if(!in[i]c[i]0)ansc[i];for(int i1;ie;i)for(int j1;je;j) if(edge[i][j]!in[i]!in[j])add_edge(i,j,edge[i][j]);
}
int main()
{init();top_sort();build_graph();net_flow();printf(%d,ans);
}
