蒟蒻求教
查看原帖
蒟蒻求教
101042
zhz小蒟蒻楼主2020/8/1 21:29

RTRT,不知道哪里写错了

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 1011
#define M 300011
#define inf 1<<30
using namespace std;
struct Node{
	int t;
	int val;
	int next;
}node[M<<1];
struct Pre{
	int t;
	int val;
	int next;
}pre[M];
int maxflow=0,bian[M][2],val[32][32],tto=0;
int ru[N],cur[N],head[N],tot,inque[N],book[N],dep[N],n,m,s,t;
int _solve(int x,int y){return (x-1)*m+y;}
void add1(int x,int y)
{
	pre[++tot].t=y;
	pre[tot].next=head[x];
	head[x]=tot;
	ru[y]++;
}
void add2(int x,int y,int z)
{
	node[++tot].t=y;
	node[tot].val=z;
	node[tot].next=head[x];
	head[x]=tot;
}
bool bfs(){
	queue<int>q;
	for(int i=1;i<=N;++i) dep[i]=0x3f3f3f3f,cur[i]=head[i],inque[i]=0;
	dep[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=node[i].next)
		{
			int v=node[i].t;
			if(dep[v]>dep[u]+1&&node[i].val!=0)
			{
				dep[v]=dep[u]+1;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dep[t]!=0x3f3f3f3f;
}
int dfs(int step,int flow)
{
	int rlow=0,used=0;
	if(step==t)
	{
		maxflow+=flow;
		return flow;
	}
	for(int i=cur[step];i;i=node[i].next)
	{
		cur[step]=i;
		int v=node[i].t;
		if(dep[v]==dep[step]+1&&node[i].val!=0)
		{
			if(rlow=dfs(v,min(node[i].val,flow-used)))
			{
				used+=rlow;
				node[i].val-=rlow;
				node[i^1].val+=rlow;
				if(used==flow) break;
			}
		}
	}
	return used;
}
void Dinic()
{
	while(bfs())
		dfs(s,1<<30);
	return;
}
void tuopu()
{
	queue<int>q;
	for(int i=1;i<=n*m+1;++i) 
		if(!ru[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		book[u]=1;
		q.pop();
		for(int i=head[u];i;i=pre[i].next)
		{
			int v=pre[i].t;
			ru[v]--;
			if(ru[v]==0&&!book[v])
			{
				book[v]=1;
				q.push(v);
			}
		}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int sum=0;
	scanf("%d %d",&n,&m);
	s=1001,t=1002;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			scanf("%d",&val[i][j]);
			int w=0;
			scanf("%d",&w);
			for(int k=1;k<=w;++k)
			{
				int x,y,A=_solve(i,j),B;
				scanf("%d %d",&x,&y);
				++x;++y;
				B=_solve(x,y);
				add1(A,B);
				bian[++tto][0]=_solve(i,j);bian[tto][1]=_solve(x,y);
			}
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=m;j>1;--j)
			add1(_solve(i,j),_solve(i,j-1));
	tuopu();
	tot=1;
	memset(head,0,sizeof(head));
	for(int i=1;i<=n;++i)
		for(int j=m;j>=1;--j)
		{
			int A=_solve(i,j),B=_solve(i,j-1);
			if(!book[A] || (!book[B] && j!=1)) continue;
			if(j!=1) 
			{
				add2(B,A,inf),add2(A,B,0);
			}
			if(val[i][j]>0)
			{
				add2(s,A,val[i][j]),add2(A,s,0),sum+=val[i][j];
			}
			else if(val[i][j]<0)
			{
				add2(A,t,-1*val[i][j]),add2(t,A,0);
			}
		}
	for(int i=1;i<=tto;++i)
	{
		if(!book[bian[i][0]]||!book[bian[i][1]]) continue;
		add2(bian[i][1],bian[i][0],inf);add2(bian[i][0],bian[i][1],0);
	}
	Dinic();
	int ans=0;
	ans=max(ans,sum-maxflow);
	printf("%d",ans);
	return 0;
}
2020/8/1 21:29
加载中...