Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以 在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
费用流，点拆开连1的边权，每条边边权1费用为路程，跑一边即可。
#include#include #include #include #include #include using namespace std;typedef long long ll;const int INF=1e9;const int N=505,M=1e6+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int S,T,n,m;struct node{ int nxt,to,w,b;}edge[M];int head[N],cnt=-1;inline void add(int u,int v,int w,int b){ edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].b=b; edge[cnt].nxt=head[u];head[u]=cnt; edge[++cnt].to=u;edge[cnt].w=0;edge[cnt].b=-b; edge[cnt].nxt=head[v];head[v]=cnt;}int dis[N];bool vis[N];inline bool spfa(int s,int t){ deque q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0;q.push_back(t);vis[t]=1; while(!q.empty()){ int u=q.front(); q.pop_front();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; int b=edge[i].b; if(edge[i^1].w&&dis[v]>dis[u]-b){ dis[v]=dis[u]-b; if(!vis[v]){ vis[v]=1; if(!q.empty()&&dis[v]
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：+
+++++++++++++++++++++++++++++++++++++++++++