[文章目录]
Description
给出一张有边权的有向图，询问1~n最多有多少条经过的点互相不重的路径，并且在路径条数最多的情况下，输出最小路程。
将每个点拆点限流，1~n的最大流即为答案，又因为每条路径流量最大为1，所以将长度设为边的费用，所得到的最小费用即为最小路程。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,head[410],to[50000],nxt[50000],f[50000],w[50000],cnt=1;
int ans,cos;
inline void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=1;
w[cnt]=z;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
f[cnt]=0;
w[cnt]=-z;
}
int dis[410],path[410];
bool v[410];
queue<int>q;
bool spfa()
{
memset(dis,0x3f,sizeof dis);
while(!q.empty()) q.pop();
memset(v,0,sizeof v);
dis[s]=0; q.push(s); v[s]=1;
int x,y;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]>dis[x]+w[i])
{
dis[y]=dis[x]+w[i];
path[y]=i^1;
if(!v[y]) q.push(y),v[y]=1;
}
}
return dis[t]<0x3f3f3f3f;
}
void minflow()
{
while(spfa())
{
int tmp=1<<30;
for(int i=t;i!=s;i=to[path[i]]) tmp=min(tmp,f[path[i]^1]);
ans+=tmp;
for(int i=t;i!=s;i=to[path[i]])
{
f[path[i]]+=tmp; f[path[i]^1]-=tmp;
cos+=w[path[i]^1]*tmp;
}
}
}
int main()
{
scanf("%d%d",&n,&m);s=1+n,t=n;
for(int i=1;i<=n;i++) add(i,i+n,0);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x+n,y,z);
}
minflow();
printf("%d %d\n",ans,cos);
return 0;
}