网络流复习计划第四题,前几天在复习全国公认挂科率最高的数电,所以一直没做题。

扯一个,数电最后没复习好正打算放弃的时候被老友傻炮拉了一把。应该可以过。

题意:
给你很多任务,每个任务都需要一台机器花费给定的时间才能完成,并且限定了每个任务的完成时间区间( 比如说 [a,b] 在第a天开始,在第b天之前完成,包括b),一台机器一天只能执行一个任务,有多台机器。问你是否能全部完成任务。

思路:
先歪一个……一开始我看到这题想了一下是想贪心做的,结果在写的过程中就自己 否定–更改 了好几次,结果还是没写出来。
实际上这道题是网络流建图的一道经典题,我们让每一个任务作为流量源点,将每个流量源点与其任务时间区间的每个数建边,流量为1,表示你可以在这个区间内其中任意一天使用一台机器,而每台机器将其作为汇点汇入一个超级汇点即可。
他的数据范围最大都只有500,因为要新建流量源点,所以所有节点数量不超过1000。我觉得复杂度还可以啊,但是discuss里面一堆人都说卡时间,过不去……感觉很奇怪,我是1A的,263s,还没有特意去记录点数,懒得优化……

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n, m, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int i = 0; i <= 1001; i++)
            if (flow[u][i] && level[i] == -1) {
                level[i] = level[u] + 1;
                que[r++] = i;
            }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& i = cur[u]; i <= 1001; i++) {
        if (flow[u][i] > 0 && level[i] == level[u] + 1
            && (cflow = dfs(i, min(low, flow[u][i])))) {
            flow[u][i] -= cflow;
            flow[i][u] += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    st = 0, en = 1001;
    int ans = 0, cflow;
    while (bfs()) {
        memset(cur, 0, sizeof cur);
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int T, s, e, len;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d", &m, &n);
        memset(flow, 0, sizeof flow);
        int sum = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d %d", &len, &s, &e);
            sum += len;
            flow[0][500 + i] = len;
            for (int j = s; j <= e; j++)
                flow[500 + i][j] = 1;
        }
        for (int i = 1; i <= 500; i++)
            flow[i][1001] = n;
        printf("Case %d: %s\n\n", cas,dinic()==sum?"Yes":"No");
    }
    return 0;
}