题目链接:Luogu P2153/BZOJ 1877/SDOI 2009
给出一张图,求最多的互不重叠的从 1 到 n 的路径,使得路径权值和最小。
题目
题目描述
Elaxia 最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等等,不过到目前为止,他坚持下来的只有晨跑。现在给出一张学校附近的地图,这张地图中包含 $ n $ 个十字路口和 $ m $ 条街道,Elaxia 只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia 每天从寝室出发跑到学校,保证寝室编号为 1,学校编号为 $ n $。Elaxia 的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路口。Elaxia 耐力不太好,他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天数尽量长。除了练空手道,Elaxia其他时间都花在了学习和找 MM 上面,所有他想请你帮忙为他设计一套满足他要求的晨跑计划。
数据范围
$$ n \leq 200, m \leq 20000$$
时空限制
$$
\text{Luogu P2153}: 1 \text{s} / 125 \text{MiB}\
\text{BZOJ 1877}: 4 \text{s} / 64 \text{MiB}
$$
题解
思路
首先我们发现需要求路程最短,天数尽量长。那么我们可以考虑最小费用最大流,其中路程为费用,天数为流量。
题目要求:
- 天数尽量长(路径尽量多),路程尽量短;
- 每个点只能访问 1 次;
- 路径不可重叠。
应对措施:
- 天数尽量长(路径尽量多),路程尽量短;
最小费用最大流。 - 每个点只能访问 1 次;
进行拆点,将 $ i $ 拆成 $ i $ 和 $ i + n $,连一条边 $ < i , i + n > $,容量为 1,费用为 0。 - 路径不可重叠。
每条路径的容量为 1 。
然后直接跑网络流即可,注意拆点后源点是 $ n + 1 $,汇点是 $ n $。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; typedef unsigned long long ull; #define INF 0X3F3F3F3F #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg bool f=false; reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return f?-res:res; } const int MAXN=200+5; //数据范围 const int MAXM=20000+5; //数据范围 inline void Read(void); inline void Work(void); int main(void){ Read(); Work(); return 0; } int n,m,s,t; // s 和 t 分别代表源点和汇点 int cnt=1,head[MAXN*2],to[MAXM*2+MAXN*2],w[MAXM*2+MAXN*2],Next[MAXM*2+MAXN*2],p[MAXM*2+MAXN*2]; //邻接表,注意 cnt 从 1 开始 inline void Add_Edge(reg int u,reg int v,reg int len,reg int val){ Next[++cnt]=head[u]; to[cnt]=v; w[cnt]=len; p[cnt]=val; head[u]=cnt; return; } inline void Add_Tube(reg int u,reg int v,reg int len,reg int val){ //方便加边 Add_Edge(u,v,len,val); //正常边 Add_Edge(v,u,0,-val); //反向边 return; } inline void Read(void){ n=read(),m=read(),s=n+1,t=n; //注意源点和汇点 for(reg int i=1;i<=m;++i){ static int a,b,c; a=read(),b=read(),c=read(); Add_Tube(a+n,b,1,c); //加边 } for(reg int i=1;i<=n;++i) Add_Tube(i,i+n,1,0); //拆点之间的边 return; } bool inque[MAXN*2]; int dis[MAXN*2]; queue<int> Q; inline bool SPFA(int s,reg int t){ //求最短路,检测汇点是否可达 memset(inque,false,sizeof(inque)); //初始化 memset(dis,0X3F,sizeof(dis)); //初始化 while(!Q.empty())Q.pop(); //初始化 inque[s]=true,dis[s]=0,Q.push(s); //起(源)点 while(!Q.empty()){ reg int ID=Q.front(); Q.pop(); inque[ID]=false; for(reg int i=head[ID];i;i=Next[i]){ if(w[i]&&dis[to[i]]>dis[ID]+p[i]){ dis[to[i]]=dis[ID]+p[i]; //求最短路 if(!inque[to[i]]){ inque[to[i]]=true; Q.push(to[i]); } } } } return dis[t]!=INF; //汇点是否可达 } bool vis[MAXN*2]; int Cost=0; int cur[MAXN*2]; inline int DFS(reg int ID,reg int t,reg int flow){ if(ID==t){ Cost+=flow*dis[t]; //到达汇点,加上费用 return flow; //返回流量 } vis[ID]=true; //用 vis[] 防止费用为零的反复横跳 reg int res=0; for(reg int &i=cur[ID];i;i=Next[i]){ //当前弧优化 if(w[i]&&dis[to[i]]==dis[ID]+p[i]&&!vis[to[i]]){ reg int f=DFS(to[i],t,min(flow-res,w[i])); if(f){ res+=f; w[i]-=f; w[i^1]+=f; if(flow-res==0) break; } } } vis[ID]=false; //回溯 return res; } inline int Dinic(reg int s,reg int t){ //求最小费用最大流 reg int MaxFlow=0; while(SPFA(s,t)){ memcpy(cur,head,sizeof(head)); //别忘了复制 head[] 到 cur[] MaxFlow+=DFS(s,t,INF); //增广 } return MaxFlow; } inline void Work(void){ reg int ans=Dinic(s,t); printf("%d %d\n",ans,Cost); //输出答案 return; }
近期评论