上海网站改版哪家好,安新建设局网站,网站开发之美,汉寿做网站的公司P2469 [SDOI2010]星际竞速
题意#xff1a;
有n个点#xff0c;m个边#xff0c;边是单向边(只能从小编号点到大编号点)#xff0c;你也可以花费ai直接到达点i。问将1~n所有点都经过一边最小费用是多少#xff1f;
题解#xff1a;
最小费用最大流#xff0c;网络流…P2469 [SDOI2010]星际竞速
题意
有n个点m个边边是单向边(只能从小编号点到大编号点)你也可以花费ai直接到达点i。问将1~n所有点都经过一边最小费用是多少
题解
最小费用最大流网络流的题都是板子题那就难在如何建边 先说结论 拆点i为ixi_xix和iyi_yiy
s-1x1_x1x~nxn_xnx流量1费用0s-1y1_y1y~nyn_yny流量1费用aia_iai1y1_y1y~nyn_yny-t流量1费用0uxu_xux-nyn_yny流量1费用w
回顾最小路径覆盖问题 原图用n条路径覆盖每条边只经过每个节点。 现在尽量合并更多的路径(即将两个路径通过一条边首尾相连)可以直到每合并两条路径图中路径的覆盖数就会减1. 最小路径覆盖的解决方法就是将n个点拆成iii和i′ii′然后源点向所有点i连一条容量为1的边再由所有的i′ii′点向汇点连一条容量为1的边对于每条边u-v由u向v′vv′连一条容量为1的边跑一边最大流n减去最大流就是最小路径覆盖 本题就是运行这种思想
代码
#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includequeue
#define ll long long
#define inf 50000000
#define re register
using namespace std;
struct po
{int from,to,dis,nxt,w;
}edge[250001];
int head[250001],cur[1000001],dep[60001],n,m,s,t,u,num-1,x,y,l,tot,sum,k,fa[10001];
int dis[5001],vis[5001],xb[5001],flow[5001];
inline int read()
{int x0,c1;char ch ;while((ch9||ch0)ch!-)chgetchar();while(ch-)c*-1,chgetchar();while(ch9ch0)xx*10ch-0,chgetchar();return x*c;
}
inline void add_edge(int from,int to,int w,int dis)
{edge[num].nxthead[from];edge[num].fromfrom;edge[num].toto;edge[num].ww;edge[num].disdis;head[from]num;
}
inline void add(int from,int to,int w,int dis)
{add_edge(from,to,w,dis);add_edge(to,from,0,-dis);
}
inline bool spfa()
{memset(dis,100,sizeof(dis));memset(vis,0,sizeof(vis));queueint q;while(!q.empty())q.pop();for(re int i1;in;i){fa[i]-1;}vis[s]1;dis[s]0;fa[s]0;flow[s]inf;q.push(s);while(!q.empty()){int uq.front();q.pop();vis[u]0;for(re int ihead[u];i!-1;iedge[i].nxt){int vedge[i].to;if(edge[i].w0dis[v]dis[u]edge[i].dis){dis[v]dis[u]edge[i].dis;fa[v]u;xb[v]i;flow[v]min(flow[u],edge[i].w);if(!vis[v]){vis[v]1,q.push(v);}}}}return dis[t]inf;
}
inline void max_flow()
{while(spfa()){int kt;while(k!s){edge[xb[k]].w-flow[t];edge[xb[k]^1].wflow[t];kfa[k];}totflow[t];sumflow[t]*dis[t];}
}
int main()
{memset(head,-1,sizeof(head));int d;nread();mread();s0;t2*n1;for(int i1;in;i){int x;scanf(%d,x);add(s,i,1,0);add(s,in,1,x);add(in,t,1,0);}for(re int i1;im;i){xread();yread();l1;dread();if(xy)swap(x,y);add(x,ny,l,d);}max_flow();coutsum;
}
