[HZNOI #koishi] Magic

2019-03-28 约 889 字预计阅读 2 分钟

迁移提示

本文迁移自博客园, 原文链接

[HZNOI #514] Magic

题意

给定一个 $n$ 个点 $m$ 条边的有向图, 每个点有两个权值 $a_i$ 和 $b_i$, 可以以 $b_i$ 的花费把第 $i$ 个点的 $a_i$ 变成 $0$. 最后每个点 $i$ 产生的花费为所有从 $i$ 出发能通过一条有向边直接到达的点 $j$ 的 $a_j$ 的 $\max$. 最小化这个过程中的总花费.

$n\le 1000,m\le50000$

题解

一点都不套路的最小割.

果然我是不会网络流的.

对于每个点, 如果将它的邻接点按照 $a_j$ 降序排序的话, 不难发现必然要干掉一个前缀的所有 $a_j$ 才能让这个点在最后统计的时候产生的花费变小. 但是多次干掉同一个点不能重复计算花费.

那么我们一点都不自然地想到最小割. 先把所有点拆成两个, 一个负责计算最终统计时的花费 (A类点), 一个负责计算被干掉的时候产生的花费 (B类点). 被干掉的时候产生的花费直接连一条流量为 $b_i$ 的边到 $t$ 就可以了. 最终统计时的花费先从 $s$ 连一条 $\infty$ 边到当前点, 然后按照 $a_j$ 降序拉出一条链来, 链上的每个点代表一条边, 权值为这条边到达的点的 $a_j$. 然后再从链上的每个点连一条 $\infty$ 边到 $j$ 对应的点. 这样的话如果 $s\verb|-|t$ 被割断, 那么对于每一个 A 类点, 后面必然是割掉了某个 $a_j$, 同时所有大于被割断的 $a_j$ 的边邻接的点必然都已经被割掉了 $b_i$.

建图Dinic就可以了.

这个拉链然后最小割的套路依然没有学会…果然我还是太菜了QAQ…

什么你问我 $n+m$ 个点Dinic怎么跑过去的? 我怎么知道?Dinic的运行速度大概都是靠信仰吧…

恋恋世界第一!

参考代码

  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


#include <bits/stdc++.h>

const int MAXV=1e5+10;
const int MAXE=5e6+10;
const int INF=0x7FFFFFFF;

struct Edge{
	int from;
	int to;
	int flow;
	Edge* rev;
	Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* cur[MAXV];
Edge* top=E;

int v;
int e;
int a[1010];
int b[1010];
int depth[MAXV];
std::vector<int> link[1010];

bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
void Insert(int,int,int);

int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	scanf("%d%d",&v,&e);
	for(int i=1;i<=v;i++)
		scanf("%d",a+i);
	for(int i=1;i<=v;i++)
		scanf("%d",b+i);
	for(int i=0;i<e;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		link[a].push_back(b);
	}
	for(int i=1;i<=v;i++)
		std::sort(link[i].begin(),link[i].end(),[](int a,int b){return ::a[a]>::a[b];});
	int s=0,t=1,cnt=v*2+1;
	for(int i=1;i<=v;i++){
		Insert(s,i+1,INF);
		Insert(i+v+1,t,b[i]);
		int last=i+1;
		for(size_t j=0;j<link[i].size();j++){
			++cnt;
			Insert(cnt,v+link[i][j]+1,INF);
			Insert(last,cnt,a[link[i][j]]);
			last=cnt;
		}
	}
	printf("%d\n",Dinic(s,t));
	return 0;
}

int Dinic(int s,int t){
	int ans=0;
	while(BFS(s,t))
		ans+=DFS(s,INF,t);
	return ans;
}

bool BFS(int s,int t){
	memset(depth,0,sizeof(depth));
	std::queue<int> q;
	q.push(s);
	depth[s]=1;
	cur[s]=head[s];
	while(!q.empty()){
		s=q.front();
		q.pop();
		for(Edge* i=head[s];i!=NULL;i=i->next){
			if(i->flow>0&&depth[i->to]==0){
				depth[i->to]=depth[s]+1;
				cur[i->to]=head[i->to];
				if(i->to==t)
					return true;
				q.push(i->to);
			}
		}
	}
	return false;
}

int DFS(int s,int flow,int t){
	if(s==t||flow<=0)
		return flow;
	int rest=flow;
	for(Edge*& i=cur[s];i!=NULL;i=i->next){
		if(i->flow>0&&depth[i->to]==depth[s]+1){
			int tmp=DFS(i->to,std::min(rest,i->flow),t);
			if(tmp<=0)
				depth[i->to]=0;
			rest-=tmp;
			i->flow-=tmp;
			i->rev->flow+=tmp;
			if(rest<=0)
				break;
		}
	}
	return flow-rest;
}

inline void Insert(int from,int to,int flow){
	top->from=from;
	top->to=to;
	top->flow=flow;
	top->rev=top+1;
	top->next=head[from];
	head[from]=top++;
	
	top->from=to;
	top->to=from;
	top->flow=0;
	top->rev=top-1;
	top->next=head[to];
	head[to]=top++;
}

目录

[HZNOI #koishi] Magic

[HZNOI #514] Magic

题意

题解

参考代码