[TJOI2015]线性代数（网络流）

[TJOI2015]线性代数（最大权闭合子图，网络流）

为了提高智商,ZJY开始学习线性代数。她的小伙伴菠萝给她出了这样一个问题:给定一个n*n的矩阵B和一个1×n的矩阵C。求出一个1×n的01矩阵A。使得\(D=(A×B−C)×A^T\)最大,其中 \(A^T\) 为A的转置。输出D。

这相当于：若同时选择X和Y，获得\(B[x][y]\)收益，若选择了X，需要\(C[x]\)的代价。然后，仿效前面那道题的做法，这道题目就是一个最大闭合权子图（满足用割选择一些点，并且有些点必选的条件）。

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=3e5+5, maxm=1e6+5, INF=1e9;

int n, m, src, dst, ans;

inline int min(int x, int y){ return x<y?x:y; }

struct Edge{

	int to, nxt, f;

}e[maxm*2];

int fir[maxn], cnte=1;

void addedge(int x, int y, int v){

	Edge &ed=e[++cnte];

	ed.to=y; ed.nxt=fir[x]; ed.f=v; fir[x]=cnte;

}

int q[maxn], head, tail, dep[maxn];

bool bfs(){

	memset(dep, 0, sizeof(dep)); dep[src]=1;

	head=tail=0; q[tail++]=src; int u;

	while (head<tail){

		u=q[head++];

		for (int i=fir[u]; ~i; i=e[i].nxt)

			if (e[i].f&&!dep[e[i].to]){

				dep[e[i].to]=dep[u]+1;

				q[tail++]=e[i].to;

			}

	}

	return dep[dst];

}

int cur[maxn];

int dfs(int u, int flow){

	if (u==dst) return flow;

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

	if (dep[e[i].to]==dep[u]+1&&e[i].f){

		int minm=dfs(e[i].to, min(flow, e[i].f));

		e[i].f-=minm; e[i^1].f+=minm;

		if (minm) return minm;

	}

	return 0;

}

int Dinic(){

	int ans=0, t;

	while (bfs()){

		memcpy(cur, fir, sizeof(fir));

		while (t=dfs(src, INF)) ans+=t;

	}

	return ans;

}

int main(){

	memset(fir, -1, sizeof(fir));

	scanf("%d", &n); int t;

	src=0; dst=n*(n+1)+1;

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

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

			scanf("%d", &t); ans+=t;

			addedge(src, i*n+j, t); addedge(i*n+j, src, 0);

			addedge(i*n+j, i, INF); addedge(i, i*n+j, 0);

			addedge(i*n+j, j, INF); addedge(j, i*n+j, 0);

		}

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

		scanf("%d", &t);

		addedge(i, dst, t); addedge(dst, i, 0);

	}

	ans-=Dinic();

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

	return 0;

}

巴特西

[TJOI2015]线性代数（网络流）

[TJOI2015]线性代数（最大权闭合子图，网络流）

最新文章

热门文章