题目描述：

N个任务，每个任务i，从时间fi开始，ti结束，价值是vi，每天执行的任务在时间上不能有重叠，一共可以而执行m天，问你最大的价值是多少。

解题报告：

M天就是容量，最多m条通路。

然后利用排好序的任务时间节点，利用图的有向性，保证时间的不相交。

具体建图如下：

每个任务有两个时间：开始和结束，一共有2n时间点。排序。

排好序后，按时间顺序依次连接，容量为无穷，费用0

源点S，副源点S2，S到S2容量为m，限制m天

S2到所有时间节点容量无穷，费用0

所有时间节点到汇点t，容量无穷，费用0

对于每个任务，从开始节点到结束几点，容量1，费用-vi（最小费用求最大值）

代码如下：

 

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define size 5000

#define Max 0x7fffffff

struct edge{int from, to, val, next, cost;} e[1000000];

int v[size], cnt, pre[size], pos[size], dis[size], que[size * 100], vst[size];

void insert(int from, int to, int val, int cost)

{

    e[cnt].from = from, e[cnt].to = to, e[cnt].val = val;

    e[cnt].cost = cost, e[cnt].next = v[from];v[from] = cnt++;

    e[cnt].from = to, e[cnt].to = from;e[cnt].val = 0;

    e[cnt].cost = -cost, e[cnt].next = v[to];v[to] = cnt++;

}

bool spfa(int s, int t, int n)

{

    memset(pre, -1, sizeof(pre)); memset(vst, 0, sizeof(vst));

    int head, tail; head = tail = 0;

    for(int i = 0; i < n; i++) dis[i] = Max;

    que[tail++] = s; pre[s] = s; dis[s] = 0; vst[s] = 1;

    while(head != tail)

    {

        int id = que[head++]; vst[id] = 0;

        id = v[id];

        while(id != -1)

        {

            if (e[id].val > 0 && dis[e[id].from] + e[id].cost < dis[e[id].to])

            {

                dis[e[id].to] = dis[e[id].from] + e[id].cost;

                pre[e[id].to] = e[id].from; pos[e[id].to] = id;

                if (!vst[e[id].to])

                {

                    vst[e[id].to] = 1;

                    que[tail++] = e[id].to;

                }

            }

            id = e[id].next;

        }

    }

    return pre[t] != -1 && dis[t] < Max;

}

int MinCostFlow(int s, int t, int n)

{

    int flow = 0, cost = 0;

    while(spfa(s, t, n))

    {

        //cout << "asdf" << endl;

        int fl = Max;

        for(int i = t; i != s; i = pre[i])

            if (e[pos[i]].val < fl) fl = e[pos[i]].val;

        flow += fl; cost += dis[t] * fl;

        for(int i = t; i != s; i = pre[i])

        {

            e[pos[i]].val -= fl;

            e[pos[i] ^ 1].val += fl;

        }

    }

    return cost; // flow是最大流值

}

int n ,m, mp[size], cost[size];

struct pint

{

    int a, b, c, id;

}tm[size];

bool cmp(pint a, pint b)

{

    if (a.a != b.a) return a.a < b.a;

    if (a.b != b.b) return a.b < b.b;

    if (a.c != b.c) return a.c < b.c;

    return true;

}

bool equ(pint a, pint b)

{

    return a.a == b.a && a.b == b.b && a.c == b.c;

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        for(int i = 0; i < n; i++)

        {

            scanf("%d:%d:%d %d:%d:%d %d", &tm[2 * i].a, &tm[2 * i].b, &tm[2 * i].c, &tm[2 * i + 1].a, &tm[2 * i + 1].b, &tm[2 * i + 1].c, &cost[i]);

            tm[2 * i].id = 2 * i;

            tm[2 * i + 1].id = 2 * i + 1;

            mp[2 * i] = 2 * i;

            mp[2 * i + 1] = 2 * i + 1;

        }

        sort(tm, tm + 2 * n, cmp);

        int pre = -1;

        for(int i = 0; i < 2 * n; i++)

        {

            mp[tm[i].id] = i;

            if (i == 0) pre = i;

            else if (equ(tm[i], tm[i - 1]))

            {

                mp[tm[i].id] = pre;

            }else pre = i;

        }

        int s = 2 * n, s2 = 2 * n + 1, t = 2 * n + 2;

        int num = 2 * n + 3;

        for(int i = 0; i < num; i++) v[i] = -1;

        cnt = 0;

        for(int i = 0; i < 2 * n - 1; i++)

            insert(i, i + 1, m, 0);

        for(int i = 0; i < n; i++)

        {

            insert(s2, mp[i * 2], m, 0);

            insert(mp[i * 2 + 1], t, m, 0);

        }

        insert(s, s2, m, 0);

        for(int i = 0; i < n; i++)

            insert(mp[i * 2], mp[i * 2 + 1], 1, -cost[i]);

        printf("%d\n", MinCostFlow(s, t, num) * -1);

    }

    return 0;

}