题目链接：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. 天数尽量长（路径尽量多），路程尽量短；
2. 每个点只能访问 1 次；
3. 路径不可重叠。

应对措施：

1. 天数尽量长（路径尽量多），路程尽量短；
   最小费用最大流。
2. 每个点只能访问 1 次；
   进行拆点，将 $ i $ 拆成 $ i $ 和 $ i + n $，连一条边 $ < i , i + n > $，容量为 1，费用为 0。
3. 路径不可重叠。
   每条路径的容量为 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;
}