[SDOI2009]晨跑 题解
题目地址:洛谷:【P2153】[SDOI2009]晨跑 – 洛谷、BZOJ:Problem 1877. — [SDOI2009]晨跑
题目描述
Elaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校,保证寝室编号为1,学校编号为N。 Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路口。Elaxia耐力不太好,他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天 数尽量长。 除了练空手道,Elaxia其他时间都花在了学习和找MM上面,所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
存在 1→n 的边存在。这种情况下,这条边只能走一次。
输入输出格式
输入格式:
第一行:两个数N,M。表示十字路口数和街道数。 接下来M行,每行3个数a,b,c,表示路口a和路口b之间有条长度为c的街道(单向)。
输出格式:
两个数,第一个数为最长周期的天数,第二个数为满足最长天数的条件下最短的路程长 度。
输入输出样例
输入样例#1:
7 10 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 4 6 1 2 5 5 3 6 6 5 7 1 6 7 1
输出样例#1:
2 11
说明
对于30%的数据,N ≤ 20,M ≤ 120。
对于100%的数据,N ≤ 200,M ≤ 20000。
题解
打个MCMF板子练练手。
最小费用最大流的裸题,对每个点拆点限制流量为1即可,天数就是最大流,路程长度就是费用。注意1和n两个点不能拆点,加边的时候特判一下。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005, INF = 1e9;
struct Edge {
int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;
inline void addedge(int u, int v, int cap, int cost) {
gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}
int n, m;
int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];
inline bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memset(f, 0, sizeof(f));
dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
while(!que.empty()) {
int u = que.front(); que.pop(); inque[u] = false;
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
dis[v] = dis[u] + gra[i].cost;
f[v] = std::min(gra[i].cap, f[u]);
pre[v] = u; pree[v] = i;
if(!inque[v]) {
inque[v] = true; que.push(v);
}
}
}
}
return f[t] != 0;
}
int flow, cost;
inline void mcmf(int s, int t) {
while(spfa(s, t)) {
for(int i = t; i != s; i = pre[i]) {
gra[pree[i]].cap -= f[t];
gra[pree[i] ^ 1].cap += f[t];
}
flow += f[t]; cost += dis[t] * f[t];
}
}
int a, b, c;
int main() {
memset(head, -1, sizeof(head));
n = readint(); m = readint();
for(int i = 2; i < n; i++) {
addedge(i, i + n, 1, 0);
}
for(int i = 1; i <= m; i++) {
a = readint(); b = readint(); c = readint();
if(a == 1) addedge(1, b, 1, c);
else addedge(a + n, b, 1, c);
}
mcmf(1, n);
printf("%d %d", flow, cost);
return 0;
}