关键词：
二次联通门 : BZOJ 1877: [SDOI2009]晨跑
/*
BZOJ 1877: [SDOI2009]晨跑
拆点 + 费用流
*/
#include <cstdio>
#include <iostream>
#define rg register
inline void read (int &n) {
rg char c = getchar ();
for (n = 0; !isdigit (c); c = getchar ());
for (; isdigit (c); n = n * 10 + c - ‘0‘, c = getchar ());
}
int S, T;
#define Max 7000
#define INF 1e9
namespace net {
const int MaxE = 2000000;
int _n[MaxE], _v[MaxE], list[Max], _f[MaxE], _c[MaxE], EC = 1, d[Max], q[MaxE], pre[Max];
bool is[Max]; int c[Max];
inline void In (int u, int v, int f, int c) {
_v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _f[EC] = f, _c[EC] = c;
_v[++ EC] = u, _n[EC] = list[v], list[v] = EC, _f[EC] = 0, _c[EC] = -c;
}
bool Bfs () {
int h = 1, t = 1; q[t] = S; rg int i, n;
for (i = 0; i <= T; ++ i) d[i] = INF, is[i] = false;
for (d[S] = 0, c[S] = INF, pre[S] = 0; h <= t; ++ h)
for (n = q[h], is[n] = false, i = list[n]; i; i = _n[i])
if (d[_v[i]] > d[n] + _c[i] && _f[i]) {
d[_v[i]] = d[n] + _c[i], pre[_v[i]] = i, c[_v[i]] = std :: min (c[n], _f[i]);
if (!is[_v[i]]) q[++ t] = _v[i], is[_v[i]] = true;
}
return d[T] < INF;
}
int Do () {
int res = 0, p = 0; rg int i;
for (int x; Bfs (); ++ p) {
for (x = c[T], i = T; i != S; i = _v[pre[i] ^ 1])
_f[pre[i]] -= x, _f[pre[i] ^ 1] += x;
res += d[T] * x;
}
printf ("%d %d", p, res);
}
}
int main (int argc, char *argv[]) {
int N, M; read (N), read (M); rg int i;
S = 1, T = N << 1; int x, y, z;
net :: In (S, S + N, INF, 0), net :: In (N, T, INF, 0);
for (i = 1; i <= M; ++ i) read (x), read (y), read (z), net :: In (N + x, y, 1, z);
for (i = 2; i < N; ++ i) net :: In (i, i + N, 1, 0);
net :: Do ();
return 0;
}
bzoj1877:[sdoi2009]晨跑
BZOJ1877:[SDOI2009]晨跑DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街... 查看详情
bzoj：1877:[sdoi2009]晨跑
题解：最小费用流；拆点法；#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>usingnamespacestd;constintmaxn=1000;constintinf=100000000;intn,m;inttotn,s, 查看详情
bzoj1877：[sdoi2009]晨跑——题解(代码片段)
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一 查看详情
bzoj#1877.[sdoi2009]晨跑
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天... 查看详情
bzoj_1877_[sdoi2009]晨跑_费用流
BZOJ_1877_[SDOI2009]晨跑_费用流题意：Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口... 查看详情
bzoj1877sdoi2009晨跑费用流
题意：给定一张有向图，求1到N：1、最多有多少条不相交的路径 2、在第一问的基础上，求所有路径的最小距离和题解：拆点之后费用流裸题#include<queue>#include<cstdio>#include<cstring>#include<cstdlib>#include<climits&g... 查看详情
1877:[sdoi2009]晨跑
1877:[SDOI2009]晨跑DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道... 查看详情
1877.[sdoi2009]晨跑费用流
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天... 查看详情
费用流bzoj1877:[sdoi2009]晨跑(代码片段)
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天... 查看详情
b1877[sdoi2009]晨跑费用流(代码片段)
其实之前写过一个板子，但是一点印象都没有，所以今天重写了一下，顺便把这个题当成板子就行了。其实费用流就是把bfs换成spfa，但是中间有一个原则，就是费用优先，在费用（就是c）上跑spfa，顺便求出流量。其实理解起来... 查看详情
[sdoi2009]晨跑(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1877[算法] 不难看出，第一问要求的是最大流，第二问求的是最小费用最大流 注意建图时要将每个点拆成入点和出点，防止... 查看详情
bzoj1877晨跑（费用流）
【BZOJ1877】晨跑（费用流）题面DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字... 查看详情
[sdoi2009]晨跑
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一 查看详情
[sdoi2009]晨跑(代码片段)
题目链接1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4inlinellread()5intx=0,f=1;charch=getchar();6while(ch>‘9‘||ch<‘0‘)if(ch==‘-‘)f=-1;ch=getchar();7while(ch>=‘0‘&&a 查看详情
[sdoi2009]晨跑
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每 查看详情
luogu2153[sdoi2009]晨跑
要想限制流量，总要想着拆点。#include<iostream>#include<cstring>#include<cstdio>#include<queue>usingnamespacestd;intn,m,ss,tt,uu,vv,ww,maxFlow,minCost,cnt,hea[405],pre[405];intdis[405];consti 查看详情
洛谷p2153[sdoi2009]晨跑
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天... 查看详情
[sdoi2009]晨跑(费用流)---链表vsvector
...撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天... 查看详情