大数据 电力杆 动态条形图 sorting highcharts vue部署 vue插件库 ipex接口 map删除指定元素 android入门实例 oracle时间格式化 pythoninput python或运算 python基础教程免费 python读取本地文件 python如何定义变量 javatrim java在线教程 java中的对象 java运行环境配置 java系统时间 java配置jdk linux教程 opengl编程指南 vs2010sp1 华为线刷工具 saminside 野德天赋 苹果双微信 不屑表情包 win10wifi 批量插入数据 网卡驱动安装包 js刷新当前页 mix2s拆机 驱动程序更新 手机刷机助手 倒计时定时器 debian安装教程 浣海之核
当前位置: 首页 > 学习教程  > 编程语言

【上下界网络流】支线剧情

2020/7/24 10:27:49 文章标签:

题目

每条边至少走一次,起点为1的有向无环图,最少走的权值最小

题解

。。。明显就是源点为1的下界为1上界INF的费用流
但上下界咋做来着


有源汇需要汇向源连(INF,0)的边变成无源汇
要假设全都到了下界,然后将剩余流量改为upilowiup_i-low_i
然后看这样流进的和流出的大小关系,in>outin>out就连S>iS->i,反之连i>Ti->T
最后跑遍普通网络流即可

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=5e4+10,INF=0x3F3F3F3F;
int n,s,t,S,T;
int head[N],nex[M],to[M],fl[M],val[M],tot=1;
void build(int u,int v,int f,int w)
{
	tot++;nex[tot]=head[u];to[tot]=v;val[tot]=w;fl[tot]=f;head[u]=tot;
	tot++;nex[tot]=head[v];to[tot]=u;val[tot]=-w;fl[tot]=0;head[v]=tot;
}
int dis[N],flw[N],pre[N];
bool vis[N];
bool spfa()
{
	memset(pre,0,sizeof(pre));
	memset(vis,0,sizeof(vis));
	memset(flw,0x7f/3,sizeof(flw));
	memset(dis,0x3F,sizeof(dis));
	queue<int>q;q.push(S);
	dis[S]=0;vis[S]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=nex[i])
		{
			int v=to[i];
			if(fl[i]&&dis[v]>dis[u]+val[i])
			{
				flw[v]=min(fl[i],flw[u]);
				dis[v]=dis[u]+val[i];
				pre[v]=i;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}return dis[T]<0x3F3F3F3F;
}
int maxflow,mincost;	
void water()
{
	while(spfa())
	{
		int fw=flw[T];
		maxflow+=fw;mincost+=dis[T]*fw;
		int now=T;
		while(now!=S)
		{
			int x=pre[now];
			fl[x]-=fw;fl[x^1]+=fw;
			now=to[x^1];
		}
	}
}
int d[N];
int main()
{
	scanf("%d",&n);
	s=1,t=n+1,S=0,T=n+2;
	build(t,s,INF,0);
	for(int m,v,w,i=1;i<=n;i++)
	{
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d%d",&v,&w);
			build(i,v,INF,w);
			mincost+=w;
			d[i]--,d[v]++;
		}build(i,t,INF,0);
	}
	for(int i=1;i<=n;i++)
	if(d[i]>0)	   build(S,i,d[i],0);
	else if(d[i]<0)build(i,T,-d[i],0);
	water();
	printf("%d",mincost);
}

本文链接: http://www.dtmao.cc/news_show_50276.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?