[Luogu 3973] TJOI2015 线性代数

<题目链接>

---

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int MAXP=510,MAXN=250510,MAXM=1501000,INF=0x3f3f3f3f;

int n,m,S,T,cnt,ans,head[MAXN],cur[MAXN],dis[MAXN],c[MAXP],b[MAXP][MAXP];

struct edge

{

	int nxt,to,w;

}e[MAXM];

void AddEdge(int u,int v,int w)

{

	e[++cnt].nxt=head[u];

	e[cnt].to=v;

	e[cnt].w=w;

	head[u]=cnt;

}

void AddEdges(int u,int v,int w)

{

	AddEdge(u,v,w);

	AddEdge(v,u,0);

}

void Build(void)

{

	m=n*n,T=m+n+1;

	for(int i=1;i<=n;++i)

		for(int j=1,t;j<=n;++j)

		{

			AddEdges(S,t=n*(i-1)+j,b[i][j]);

			AddEdges(t,m+i,INF);

			AddEdges(t,m+j,INF);

		}

	for(int i=1;i<=n;++i)

		AddEdges(m+i,T,c[i]);

}

bool BFS(void)

{

	queue<int> q;

	memset(dis,0,sizeof dis);

	q.push(S);

	dis[S]=1;

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		for(int i=head[u],v;i;i=e[i].nxt)

			if(e[i].w && !dis[v=e[i].to])

			{

				q.push(v);

				dis[v]=dis[u]+1;

			}

	}

	return dis[T];

}

int DFS(int u,int k)

{

	if(u==T || !k)

		return k;

	int sum=0;

	for(int i=cur[u],v,f;i;i=e[i].nxt)

		if(e[i].w && dis[v=e[i].to]==dis[u]+1 && (f=DFS(v,min(k,e[i].w))))

		{

			cur[u]=i;

			e[i].w-=f,e[((i-1)^1)+1].w+=f;

			k-=f,sum+=f;

		}

	if(!sum)

		dis[u]=0;

	return sum;

}

void Dinic(void)

{

	int f;

	while(BFS())

		while(memcpy(cur,head,sizeof head),f=DFS(S,INF))

			ans-=f;

	printf("%d\n",ans);

}

int main(int argc,char *argv[])

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

		{

			scanf("%d",&b[i][j]);

			ans+=b[i][j];

		}

	for(int i=1;i<=n;++i)

		scanf("%d",&c[i]);

	Build();

	Dinic();

	return 0;

}