拓扑排序消圈+最大权闭合子图
因为每次僵尸都是从右往左走，那么我们对于右往左依次连边
然后每个点的攻击集合就是相当于选了攻击集合中的点就必须选择这个点。
那么我们反向建边，因为有可能出现循环保护的情况，所以先拓扑排序消圈然后按照最大权闭合子图的模型建网络流图即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #include<cstdio>#include<cstdlib>#include<algorithm>#include<queue>#include<cstring>using namespace std;int en,en1,n,m,ok[1005],cur[1005],h[1005],h1[1005],score[1005],du[1005],level[1005],S,T,now,mxval;struct Edge{int b,f,next,back;}e[1000005],e1[1000005];int Cal(int x,int y){return (x-1)*m+y;}void AddEdge1(int sa,int sb){e1[++en1].b=sb;e1[en1].next=h1[sa];h1[sa]=en1;du[sb]++;}void AddEdge(int sa,int sb,int sc){e[++en].b=sb;e[en].back=en+1;e[en].f=sc;e[en].next=h[sa];h[sa]=en;swap(sa,sb);e[++en].b=sb;e[en].back=en-1;e[en].f=0;e[en].next=h[sa];h[sa]=en;}int BFS(){queue<int> Q;Q.push(S);memset(level,0,sizeof(level));level[S]=1;while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(level[v] || !e[i].f)continue; Q.push(v); level[v]=level[u]+1; }}return level[T];}int DFS(int u,int flow){if(u==T)return flow;int f=flow;for(int &i=cur[u];i;i=e[i].next){ int v=e[i].b,fl; if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){ f-=fl; e[i].f-=fl; e[e[i].back].f+=fl; if(!f)return flow; }}return flow-f;}int Dinic(){int ans=0;while(BFS()){ for(int i=1;i<=T;i++)cur[i]=h[i]; ans+=DFS(S,2100000000);}return ans;}void Toposort(){queue<int> Q;for(int i=1;i<=now;i++){ if(!du[i]){ok[i]=1;Q.push(i);}}while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=h1[u];i;i=e1[i].next){ int v=e1[i].b; du[v]--; if(!du[v]){ok[v]=1;Q.push(v);} }}}int main(){freopen("1565.in","r",stdin);freopen("1565.out","w",stdout);scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int can; now++; scanf("%d %d",&score[now],&can); for(int k=1;k<=can;k++){ int dx,dy; scanf("%d %d",&dx,&dy); dx++;dy++; AddEdge1(now,Cal(dx,dy)); } if(j!=m)AddEdge1(now+1,now); }}Toposort();S=now+1;T=now+2;for(int i=1;i<=now;i++){ if(ok[i]){ if(score[i]>=0){AddEdge(S,i,score[i]);mxval+=score[i];} else AddEdge(i,T,-score[i]); for(int j=h1[i];j;j=e1[j].next){ int v=e1[j].b; if(ok[v])AddEdge(v,i,2100000000); } }}printf("%d\n",mxval-Dinic());return 0;} |
评论 (0)
