做网站用 jsp还是asp,c 做网站,重庆网站开发小顶网,vs2017 网站开发晨跑
题目连接
https://www.luogu.org/problemnew/show/P2153
题解
求最大不相交路径数,并在路径数最大前提下,求总路程最短.
太裸了.
求不相交路径数:将除1,n1,n1,n两点外的所有点拆分,中间连一条容量为111,费用为000的边.然后所有的原边u→vu \rightarrow vu→v视作从u…晨跑
题目连接
https://www.luogu.org/problemnew/show/P2153
题解
求最大不相交路径数,并在路径数最大前提下,求总路程最短.
太裸了.
求不相交路径数:将除1,n1,n1,n两点外的所有点拆分,中间连一条容量为111,费用为000的边.然后所有的原边u→vu \rightarrow vu→v视作从uuu的出点连向vvv的入点的一条费用为路程,容量为111的边.
从1→n1 \rightarrow n1→n跑最小费用最大流即是答案.
代码
// luogu-judger-enable-o2
#include iostream
#include algorithm
#include cstring
#include queue
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)const int inf 0x3f3f3f3f;
const int mm 111111;
const int maxn 999;
int node,src,dest,edge;
int ver[mm],flow[mm],cst[mm],nxt[mm];
int head[maxn],work[maxn],dis[maxn],q[maxn];
int tot_cost;
void prepare(int _node,int _src,int _dest)
{node_node,src_src,dest_dest;for(int i0; inode; i)head[i]-1;edge0;tot_cost 0;
}
void add_edge(int u,int v,int c,int cost)
{ver[edge]v,flow[edge]c,nxt[edge]head[u],cst[edge]cost,head[u]edge;ver[edge]u,flow[edge]0,nxt[edge]head[v],cst[edge]-cost,head[v]edge;
}
int ins[maxn];
int pre[maxn];
bool Dinic_spfa()
{memset(ins,0,sizeof(ins));memset(dis,inf,sizeof(dis));memset(pre,-1,sizeof(pre));std::queueint Q;Q.push(src);dis[src] 0,ins[src] 1;pre[src] -1;while(!Q.empty()){int u Q.front();Q.pop();ins[u] 0;for(int e head[u];e ! -1;e nxt[e]){int v ver[e];if(!flow[e]) continue;if(dis[v] dis[u] cst[e]){dis[v] dis[u] cst[e];pre[v] e;if(!ins[v]) ins[v] 1,Q.push(v);}}}return dis[dest] inf;
}
int Dinic_flow()
{int i,ret0,deltainf;while(Dinic_spfa()){for(int ipre[dest];i ! -1;i pre[ver[i^1]])delta std::min(delta,flow[i]);for(int ipre[dest];i ! -1;i pre[ver[i^1]])flow[i] - delta,flow[i^1] delta;retdelta;tot_cost dis[dest]*delta;}return ret;
}
int n,m;
int main() {std::ios::sync_with_stdio(false);std::cin n m;prepare(2*n,0,2*n-1);for(int i 1;i n;i) {if(i 1 || i n)add_edge(i-1,i-1n,inf,0);else add_edge(i-1,i-1n,1,0);}for(int i 1;i m;i) {int a,b,c;std::cin a b c;add_edge(a-1n,b-1,1,c);}int myflow Dinic_flow();std::cout myflow tot_cost std::endl;return 0;
}
