scpc2016_pre1_5.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int N, K;
#define Mi(i) i //플로우 네트워크에서 장인 i의 정점 번호
#define Ti(i) i+100 //플로우 네트워크에서 시간 [i-1, i]의 정점 번호
#define Bi(i) i+200 //플로우 네트워크에서 구두 i의 정점 번호 
#define SINK 401

struct edg{
    int to, cap, rev;
    edg(){};
    edg(int _to, int _cap, int _rev){
        to = _to, cap = _cap, rev = _rev;
    }
};
#define MAXV 450
vector<edg> graph[MAXV];

void add_edge(int s, int e, int x){
    graph[s].push_back(edg(e, x, (int)graph[e].size()));
    graph[e].push_back(edg(s, 0, (int)graph[s].size()-1));
}
bool vis[MAXV];
pair<int, int> from[MAXV];
bool dfs(int x, int sink){
    if(x == sink) return 1;
    if(vis[x]) return 0;
    vis[x] = 1;
    int p=0;
    for(int i = 0 ; i < graph[x].size(); i++){
        edg next = graph[x][i];
        if(next.cap > 0 && dfs(next.to, sink)){
            from[next.to] = make_pair(x, p);
            return 1;
        }
        p++;
    }
    return 0;
}
int match(int sink){
    int ret = 0;
    memset(vis,0,sizeof(vis));
    while(dfs(0, sink)){
        memset(vis,0,sizeof(vis));
        int pos = sink;
        while(pos){
            int rev = graph[from[pos].first][from[pos].second].rev;
            graph[from[pos].first][from[pos].second].cap--;
            graph[pos][rev].cap++;
            pos = from[pos].first;
        }
        ret++;
    }
    return ret;
}

int main(){
    setbuf(stdout, NULL);
    int T;
    scanf("%d", &T);
    for(int t =1;  t <= T; t++){
        
        
        scanf("%d%d", &N, &K);
        
        //그래프 초기화
        for(int i = 0 ; i< MAXV; i++)
            graph[i].clear();
        
        int psum = 0;
        for(int i = 1; i<= N; i++){
            int a, f, p;
            scanf("%d%d%d", &a, &f, &p);
            psum += p;
            
            //시간에서 구두로
            for(int j = a+1; j <= f; j++)
                add_edge(Ti(j), Bi(i), 1);
            
            //구두에서 sink로
            add_edge(Bi(i), SINK, p);
        }
        for(int i = 1; i<= K ; i++){
            int s, e;
            scanf("%d%d", &s, &e);
            
            //soure에서 장인으로
            add_edge(0, Mi(i), e-s);
            
            //장인에서 시간으로 연결
            for(int j = s+1; j <= e; j++)
                add_edge(Mi(i), Ti(j), 1);
        }
        
        int ans =  match(SINK);
        
        printf("Case #%d\n%d\n", t,  ans == psum );
    }
    return 0;
}