题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1877
题意：一个 n 个点，m 条边的有向图，边有边权，每天的晨跑是一条从 1 到 n 的路径，每天的晨跑不能通过（除 1，n 外）重复的点，制定一个晨跑方案使得晨跑天数最多的同时满足总路程最小...
因为在练习费用流，所以知道它是费用流... 并不显然... 这道题大概是第一道真正意义上自己建模的 水 题了...
首先题目中有一个很严格的限制，点不能重复通过，我们这样处理它：将一个点 i 拆成\(x_i\) 和\(y_i\) 两个点，分别作为该点的出入点，连接该点的出入边，这样做提供了怎样的便利呢？就是我们可以方便的表示并存储“通过这个点”这个信息了，我们用一条边去沟通\(x_i\) 和\(y_i\)，只要我们经过了这条边，就等价于通过了这个点，我们可以为这条边构造特殊的性质使得方便我们处理“一个点只能通过一次”这个约束。那么处理的方法就是显然的了，在\(x_i\) 和\(y_i\) 间连接一天流量为 1，费用为 0 的边，限制了流量自然只能跑一次。
对于题目中给出的边 (i,j)，直接建立从 i 出点到 j 入点的一条流量 1 费用为路程的边即可。
当然，需要注意的是，由于点 1 和点 n 可以无限通过，我们需要为他们拆点时连流量为 inf，费用 0 的边。
本题很巧妙的转化思想就是将路程转移到费用上，用流量来限制“流过的次数”。当然，对于第一问，我们只需要记录增广次数即可啦！~
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#define N 410 #define M 100010 #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to,val,cost; }edge[M]; int cnt=2,head[M],anscost,anscnt; void add(int from,int to,int val,int cost) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].cost=cost; edge[cnt].next=head[from]; head[from]=cnt++; } void insert(int from,int to,int val,int cost) {add(from,to,val,cost);add(to,from,0,-cost);} int n,m,S,T; void build() { n=read(),m=read(),S=1,T=n*2; for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u+n,v,1,w); } for(int i=2;i<n;i++) insert(i,i+n,1,0); insert(1,S+n,inf,0); insert(n,T,inf,0); } int dis[N],vis[N],pre[N]; queue<int> q; bool spfa() { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); dis[S]=0;vis[S]=1; q.push(S); while(!q.empty()) { int tp=q.front(); q.pop(); vis[tp]=0; for(int i=head[tp];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val,cost=edge[i].cost; if(dis[to]>dis[tp]+cost&&val) { pre[to]=i; dis[to]=dis[tp]+cost; if(!vis[to]) { vis[to]=1; q.push(to); } } } } return pre[T]!=-1; } void MCMF() { int mn=inf; for(int i=pre[T];i!=-1;i=pre[edge[i^1].to]) mn=min(mn,edge[i].val); for(int i=pre[T];i!=-1;i=pre[edge[i^1].to]) { edge[i].val-=mn,edge[i^1].val+=mn; anscost+=edge[i].cost*mn; } } int main() { build(); while(spfa()) { anscnt++; MCMF(); } printf("%d %d",anscnt,anscost); } |
Comments | NOTHING