[CQOI2015]网络吞吐量

C++(g++ 7.5.0) 解法, 执行用时: 42ms, 内存消耗: 17132K, 提交时间: 2022-12-26 13:18:49

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 510 * 510, M = 5e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;

int h[N], e[M], ne[M], f[M], idx, d[N], cur[N], n, m, S, T, a[N], dp[N], ans1, ans2, ans3;

void add(int a, int b, int c)
{
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}

bool bfs()
{
	queue<int>q;
	memset(d, -1, sizeof d);
	q.push(S);
	d[S] = 0;
	cur[S] = h[S];
	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(d[j] == -1 && f[i])
			{
				d[j] = d[t] + 1;
				cur[j] = h[j];
				if(j == T) return true;
				q.push(j);
			}
		}
	}
	return false;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; ~i && flow < limit; i = ne[i])
	{
		int j = e[i];
		if(d[j] == d[u] + 1 && f[i])
		{
			int t = find(j, min(f[i], limit - flow));
			if(!t) d[j] = -1;
			f[i] -= t, f[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int r = 0, flow;
	while(bfs()) while(flow = find(S, INF)) r += flow;
	return r;
}

typedef pair<int, int>PII;
vector<PII>g[N];
int dist[N];
bool st[N];

void dijkstra()
{
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	heap.push({0, 1});

	while(!heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		int ver = t.second;
		if(st[ver]) continue;
		st[ver] = true;
		for(auto t : g[ver])
		{
			int j = t.first, w = t.second;
			if(dist[j] > dist[ver] + w)
			{
				dist[j] = dist[ver] + w;
				heap.push({dist[j], j});
			}
		}
	}

	for(int i = 1; i <= n; i ++ )
		for(auto t : g[i])
		{
			int j = t.first, w = t.second;
			if(dist[j] == dist[i] + w)
				add(i + n, j, INF);
		}
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	S = 0, T = 2 * n + 1;
	add(S, 1, INF), add(2 * n, T, INF);
	
	for(int i = 1; i <= m; i ++ )
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w}), g[v].push_back({u, w});
	}
	dijkstra();


	for(int i = 1; i <= n; i ++ )
	{
		int x;
		cin >> x;
		if(i != x && i != n) add(i, i + n, x);
		else add(i, i + n, INF);
	}
	cout << dinic() << '\n';
}

C++ 解法, 执行用时: 32ms, 内存消耗: 2972K, 提交时间: 2022-07-07 14:43:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=4e5+5,mod=1e9+7;
const ll inf=1e15;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,cnt=1,cnt1=1,h[N],h1[N],st,ed,dep[N],cur[N],vis[N];
ll d[N];
struct edge{
	int to,nt;ll w;
}e[M],e1[M];
void add(int u,int v,ll w){
	e[++cnt]={v,h[u],w},h[u]=cnt;
	e[++cnt]={u,h[v],w},h[v]=cnt;
}
void Add(int u,int v,ll w){
	e1[++cnt1]={v,h1[u],w},h1[u]=cnt1;
	e1[++cnt1]={u,h1[v],0},h1[v]=cnt1;
}
bool bfs(){
	queue<int>q;q.push(st),mst(dep,0),dep[st]=1;
	while(!q.empty()){
		int  u=q.front();q.pop();cur[u]=h1[u];
		for(int i=h1[u];i;i=e1[i].nt){
			int v=e1[i].to;
			ll w=e1[i].w;
			if(w&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
		}
	}return dep[ed];
}
ll dfs(int u,ll c){
	if(u==ed) return c;ll res=c;
	for(int &i=cur[u];i;i=e1[i].nt){
		int v=e1[i].to;
		ll w=e1[i].w;
		if(w&&dep[v]==dep[u]+1){
			ll now=dfs(v,min(res,1LL*w));
			if(!now) dep[v]=1;
			else e1[i].w-=now,e1[i^1].w+=now,res-=now;
		}if(!res) return c;
	} return c-res;
}
void spfa(){
	queue<int>q;q.push(st),mst(d,0x3f),d[st]=0;mst(vis,0),vis[st]=1;
	while(!q.empty()){
		int u=q.front();q.pop(),vis[u]=0;
		for(int i=h[u];i;i=e[i].nt){
			ll w=e[i].w;int v=e[i].to;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=h[i];j;j=e[j].nt){
			int v=e[j].to;
			if(d[v]==d[i]+e[j].w) Add(i+n,v,inf);
		}
}
int main(){
	scanf("%d%d",&n,&m);st=1,ed=n<<1;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w),add(u,v,w);
	}
	spfa();
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		Add(i,i+n,(i==1||i==n)?inf:x);
	}ll s=0;
	while(bfs()) 
	s+=dfs(st,inf);
	printf("%lld\n",s);
	return 0;
}

详情