题目描述：有m(1000)个钢琴，p(2000)个人，第i个钢琴要在[ai,bi]天之间的某一天被运送，(1<=ai,bi<=100)，一个钢琴需要2个人运送(即每天最多可以有p/2个钢琴被运送)。

问：

能否不在周六日运完。

如果上述不能，加上周六日能否运完。

解题报告：

一开始的想法比较弱：

源点s，汇点t。

源点连接每个钢琴，容量1，表示一个钢琴只能运送一次。

每个钢琴连接[ai,bi]一共bi-a1+1个点，容量1，表示这个钢琴只能在[ai,bi]之前选一天。

每一天的点连接汇点，容量p/2，表示每一天最多运送p/2个钢琴。

周六日的限制就在于天数的节点剪掉周六日的节点即可。

看最大流是否等于钢琴的个数即可（表示所有的钢琴都被运送完）；

 

这样的话，点数就有m+100+2个，边数最坏可以由m*100个，

即1100个点，10^5条边，太多了，不过POJ还能过。。

 

优化的建模方法如下：

源点连接每一天（不连周六日就是第一问），容量为p/2，表示每一天都可以有p/2个钢琴被搬运。

对于每一天i，连接i到汇点，容量为以i为结尾的钢琴。

对于每一天i，连接i到i+1，容量为i到i+1被m个钢琴区间覆盖的次数。

这样，每个钢琴只要在最后一天前能够凑到一个人就算被搬运了。

而由于i到i+1容量的限制，保证了为a钢琴凑得人不会多于，即不会给不相交区间的b钢琴使用。

 

这样最多一共就102个点，299条边，效率提高了很多很多。

看最大流是否等于m即可，代码如下：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

using namespace std;

#define Max 0x1fffffff

#define SIZE 200

vector<pair<int, int> > jeo;

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

int v[SIZE], que[SIZE], dis[SIZE], cnt, cur[SIZE];

void insert(int from, int to, int va)

{

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

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

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

    e[cnt].next = v[to];v[to] = cnt++;

}

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

{

    int head, tail, id;

    head = tail = 0; que[tail++] = s;

    memset(dis, -1, sizeof(int) * n);dis[s] = 0;

    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]

        for(id = v[que[head++]]; id != -1; id = e[id].next)

            if (e[id].val > 0 && dis[e[id].to] == -1)

            {

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

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

                if (e[id].to == t) return true;

            }

    return false;

}

 

int Dinic(int n, int s, int t)

{

    int maxflow = 0, tmp, i;

    while(bfs(n, s, t))

    {

        int u = s, tail = 0;

        for(i = 0; i < n; i++) cur[i] = v[i];

        while(cur[s] != -1)

            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])

            {que[tail++] = cur[u]; u = e[cur[u]].to;}

            else if (u == t)

            {

                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);

                for(maxflow += tmp, i = tail - 1; i >= 0; i--)

                {

                    e[que[i]].val -= tmp;

                    e[que[i] ^ 1].val += tmp;

                    if (e[que[i]].val == 0) tail = i;

                }

                u = e[que[tail]].from;

            }

            else

            {

                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;

                cur[u] = e[cur[u]].next;

            }

    }

    return maxflow;

}

int num[SIZE], ed[SIZE];

int m, p, tt;

bool build(int a, int b)

{

    memset(v, -1, sizeof(v)); cnt = 0;

    int s = 0, t = 101;

    for(int i = 1; i <= 100; i++) if (i % 7 != a && i % 7 != b)

        insert(s, i, p / 2);

    memset(num, 0, sizeof(num)); memset(ed, 0, sizeof(ed));

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

    {

        num[jeo[i].second]++;

        for(int j = jeo[i].first; j < jeo[i].second; j++)

            ed[j]++;

    }

    for(int i = 1; i <= 100; i++)

        insert(i, t, num[i]), insert(i, i + 1, ed[i]);

    return Dinic(t + 1, s, t) == m;

}

int main()

{

    scanf("%d", &tt);while(tt--)

    {

 

        scanf("%d%d", &m, &p);

        jeo.clear();

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

        {

            int a, b;scanf("%d%d", &a, &b);

            jeo.push_back(make_pair(a, b));

        }

        if (build(6, 0)) printf("fine\n");

        else if (build(-1, -1)) printf("weekend work\n");

        else printf("serious trouble\n");

    }

         return 0;

}