1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
//based on: http://backtrack-it.blogspot.com/2013/03/max-flow-algorithm-with-sample-c-code.html
#include <cstdio>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

#define D(x)


#define MAX_NODES (101+201+101+2)           // the maximum number of nodes in the graph
#define INF 2147483646          // represents infity
#define UNINITIALIZED -1        // value for node with no parent

using namespace std;

// represents the capacities of the edges
int capacities[MAX_NODES][MAX_NODES];
// shows how much flow has passed through an edge
int flowPassed[MAX_NODES][MAX_NODES];
// represents the graph. The graph must contain the negative edges too!
vector<int> graph[MAX_NODES];
// shows the parents of the nodes of the path built by the BFS
int parentsList[MAX_NODES];
// shows the maximum flow to a node in the path built by the BFS
int currentPathCapacity[MAX_NODES];

int bfs(int startNode, int endNode)
{
	memset(parentsList, UNINITIALIZED, sizeof(parentsList));
	memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

	queue<int> q;
	q.push(startNode);

	parentsList[startNode] = -2;
	currentPathCapacity[startNode] = INF;

	while (!q.empty()) {
		int currentNode = q.front(); q.pop();

		for (int i = 0; i < graph[currentNode].size(); i++) {
			int to = graph[currentNode][i];
			if (parentsList[to] == UNINITIALIZED) {
				if (capacities[currentNode][to] - flowPassed[currentNode][to] > 0) {
					parentsList[to] = currentNode;
					currentPathCapacity[to] = min(currentPathCapacity[currentNode],
								      capacities[currentNode][to] - flowPassed[currentNode][to]);
					if (to == endNode) return currentPathCapacity[endNode];
					q.push(to);
				}
			}
		}
	}
	return 0;
}

int edmondsKarp(int startNode, int endNode)
{
	int maxFlow = 0;

	while (true) {
		int flow = bfs(startNode, endNode);
		if (flow == 0)
			break;

		maxFlow += flow;
		int currentNode = endNode;

// we update the passed flow matrix
		while (currentNode != startNode) {
			int previousNode = parentsList[currentNode];
			flowPassed[previousNode][currentNode] += flow;
			flowPassed[currentNode][previousNode] -= flow;
			currentNode = previousNode;
		}
	}

	return maxFlow;
}

void add(int from, int to, int capacity) {
    D(cout << "add node: " << from << " -> " << to << " : " << capacity << "\n");
    capacities[from][to] = capacity;
    graph[from].push_back(to);
    graph[to].push_back(from);
}

//------------------------------------

int n_tasks, cpus;
struct Task {
    int p,k,c;
    int node;
};
vector<Task> tasks;
int c_sum = 0;

int main() {
    cin >> n_tasks >> cpus;
    vector<int> values;
    for(int i=0;i<n_tasks;i++) {
        Task t;
        cin >> t.p >> t.k >> t.c;
        tasks.push_back(t);
        values.push_back(t.p);
        values.push_back(t.k);
        c_sum += t.c;
    }
    sort(values.begin(), values.end());
    auto it = unique(values.begin(), values.end());
    values.resize(std::distance(values.begin(), it));

    int source = 0, nodes = 1;
    //add tasks
    for(Task &t: tasks) {
        t.node = nodes++;
        add(source, t.node, t.c);
    }
    int first_val_node = nodes;
    nodes+=values.size();
    int first_cpu_node = nodes;
    nodes+=cpus;
    int sink = nodes;

    //add cpus
    for(int i=0;i<cpus;i++) {
        add(first_cpu_node+i, sink, INF/2);
    }
    //add values
    for(int i=0;i<values.size()-1;i++) {
        int a = values[i], b = values[i+1];
        int s = b - a;
        D(cout << "val:[" << a << "," << b << "] " << s << "\n");
        int node = i+first_val_node;
        for(Task t: tasks) {
            if(t.p<=a && t.k>=b) {
                add(t.node, node, s);
            }
        }
        for(int j = first_cpu_node;j<sink;j++) {
            add(node, j, s);
        }
    }

    int maxFlow = edmondsKarp(source, sink);
    D(cout << maxFlow  << " ?= " << c_sum << endl);
    if(maxFlow == c_sum) {
        cout << "TAK\n";
    } else {
        cout << "NIE\n";
    }
}