#include <cstdio> #include <vector> #include <algorithm> #include <set> #include <queue> #include <climits> #include <cstring> using namespace std; /*******************************************************************************/ // Poniższy kod algorytmu szukania maksymalnego przepływu (metoda push-relabel) // zapożyczony został z udostępnionej biblioteczki kodów Bartosza Walczaka. #define FOR(i,a,b) for (int i=(a); i<(int)(b); ++i) #define FORD(i,a,b) for (int i=(a)-1; i>=(int)(b); --i) #define FORE(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) const int FLOW_MAX = 305; int FLOW_N, FLOW_S, FLOW_T; int FLOW_EDGE[FLOW_MAX][FLOW_MAX]; int FLOW_LABEL[FLOW_MAX]; int FLOW_EXCESS[FLOW_MAX]; int FLOW_CUR[FLOW_MAX]; bool FLOW_INQ[FLOW_MAX]; void relabel() { queue<int> Q; fill_n(FLOW_LABEL, FLOW_N, INT_MAX-1); FLOW_LABEL[FLOW_T]=0; Q.push(FLOW_T); while (!Q.empty()) { int j=Q.front(); Q.pop(); FOR(i,0,FLOW_N) if (FLOW_LABEL[i]==INT_MAX-1 && FLOW_EDGE[i][j]) { FLOW_LABEL[i]=FLOW_LABEL[j]+1; Q.push(i); } } } int compute_flow() { FOR(i,0,FLOW_N) if (i!=FLOW_S) { FLOW_EDGE[i][FLOW_S]+=FLOW_EXCESS[i]=FLOW_EDGE[FLOW_S][i]; FLOW_EDGE[FLOW_S][i]=0; } int cnt=FLOW_N; relabel(); queue<int> Q; FOR(i,0,FLOW_N) if (i!=FLOW_S && i!=FLOW_T) { if (FLOW_EXCESS[i]) Q.push(i); FLOW_INQ[i]=FLOW_EXCESS[i]; FLOW_CUR[i]=0; } FLOW_INQ[FLOW_S]=FLOW_INQ[FLOW_T]=true; while (!Q.empty()) { int i=Q.front(); Q.pop(); FLOW_INQ[i]=false; while (FLOW_EXCESS[i] && FLOW_LABEL[i]<FLOW_N) { int j=FLOW_CUR[i]; if (j==FLOW_N) { if (--cnt) { FLOW_LABEL[i]=INT_MAX-1; FOR(k,0,FLOW_N) if (FLOW_EDGE[i][k]) FLOW_LABEL[i]=min(FLOW_LABEL[i], FLOW_LABEL[k]+1); } else { cnt=FLOW_N; relabel(); } FLOW_CUR[i]=0; } else if (FLOW_EDGE[i][j] && FLOW_LABEL[i]==FLOW_LABEL[j]+1) { int f=min(FLOW_EXCESS[i], FLOW_EDGE[i][j]); FLOW_EDGE[i][j]-=f; FLOW_EDGE[j][i]+=f; FLOW_EXCESS[i]-=f; FLOW_EXCESS[j]+=f; if (!FLOW_INQ[j]) { Q.push(j); FLOW_INQ[j]=true; } } else ++FLOW_CUR[i]; } } return FLOW_EXCESS[FLOW_T]; } /*******************************************************************************/ int n, m, task_sum; vector<int> P, K, C; set<int> PS; int main() { // Read data scanf("%d %d", &n, &m); task_sum = 0; P.resize(n); K.resize(n); C.resize(n); FOR(i, 0, n) { scanf("%d %d %d", &P[i], &K[i], &C[i]); PS.insert(P[i]); PS.insert(K[i]); task_sum += C[i]; } // Init basic data in FLOW graph FLOW_N = n + (PS.size() - 1) + 2; FLOW_S = FLOW_N - 2; FLOW_T = FLOW_N - 1; FOR(i, 0, FLOW_N) memset(FLOW_EDGE[i], 0, FLOW_N); memset(FLOW_LABEL, 0, FLOW_N); memset(FLOW_EXCESS, 0, FLOW_N); memset(FLOW_CUR, 0, FLOW_N); memset(FLOW_INQ, false, FLOW_N); FOR(i, 0, n) FLOW_EDGE[FLOW_S][i] = C[i]; // Create period nodes int prev_point = -1, node_id = n - 1; FORE(it, PS){ int period_capacity = *it - prev_point; if (prev_point != -1) { FLOW_EDGE[node_id][FLOW_T] = period_capacity * m; FOR(i, 0, n) if (prev_point >= P[i] && *it <= K[i]) FLOW_EDGE[i][node_id] = period_capacity; } prev_point = *it; ++node_id; } // Calculate result if (compute_flow() >= task_sum) printf("TAK\n"); else printf("NIE\n"); }
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 | #include <cstdio> #include <vector> #include <algorithm> #include <set> #include <queue> #include <climits> #include <cstring> using namespace std; /*******************************************************************************/ // Poniższy kod algorytmu szukania maksymalnego przepływu (metoda push-relabel) // zapożyczony został z udostępnionej biblioteczki kodów Bartosza Walczaka. #define FOR(i,a,b) for (int i=(a); i<(int)(b); ++i) #define FORD(i,a,b) for (int i=(a)-1; i>=(int)(b); --i) #define FORE(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) const int FLOW_MAX = 305; int FLOW_N, FLOW_S, FLOW_T; int FLOW_EDGE[FLOW_MAX][FLOW_MAX]; int FLOW_LABEL[FLOW_MAX]; int FLOW_EXCESS[FLOW_MAX]; int FLOW_CUR[FLOW_MAX]; bool FLOW_INQ[FLOW_MAX]; void relabel() { queue<int> Q; fill_n(FLOW_LABEL, FLOW_N, INT_MAX-1); FLOW_LABEL[FLOW_T]=0; Q.push(FLOW_T); while (!Q.empty()) { int j=Q.front(); Q.pop(); FOR(i,0,FLOW_N) if (FLOW_LABEL[i]==INT_MAX-1 && FLOW_EDGE[i][j]) { FLOW_LABEL[i]=FLOW_LABEL[j]+1; Q.push(i); } } } int compute_flow() { FOR(i,0,FLOW_N) if (i!=FLOW_S) { FLOW_EDGE[i][FLOW_S]+=FLOW_EXCESS[i]=FLOW_EDGE[FLOW_S][i]; FLOW_EDGE[FLOW_S][i]=0; } int cnt=FLOW_N; relabel(); queue<int> Q; FOR(i,0,FLOW_N) if (i!=FLOW_S && i!=FLOW_T) { if (FLOW_EXCESS[i]) Q.push(i); FLOW_INQ[i]=FLOW_EXCESS[i]; FLOW_CUR[i]=0; } FLOW_INQ[FLOW_S]=FLOW_INQ[FLOW_T]=true; while (!Q.empty()) { int i=Q.front(); Q.pop(); FLOW_INQ[i]=false; while (FLOW_EXCESS[i] && FLOW_LABEL[i]<FLOW_N) { int j=FLOW_CUR[i]; if (j==FLOW_N) { if (--cnt) { FLOW_LABEL[i]=INT_MAX-1; FOR(k,0,FLOW_N) if (FLOW_EDGE[i][k]) FLOW_LABEL[i]=min(FLOW_LABEL[i], FLOW_LABEL[k]+1); } else { cnt=FLOW_N; relabel(); } FLOW_CUR[i]=0; } else if (FLOW_EDGE[i][j] && FLOW_LABEL[i]==FLOW_LABEL[j]+1) { int f=min(FLOW_EXCESS[i], FLOW_EDGE[i][j]); FLOW_EDGE[i][j]-=f; FLOW_EDGE[j][i]+=f; FLOW_EXCESS[i]-=f; FLOW_EXCESS[j]+=f; if (!FLOW_INQ[j]) { Q.push(j); FLOW_INQ[j]=true; } } else ++FLOW_CUR[i]; } } return FLOW_EXCESS[FLOW_T]; } /*******************************************************************************/ int n, m, task_sum; vector<int> P, K, C; set<int> PS; int main() { // Read data scanf("%d %d", &n, &m); task_sum = 0; P.resize(n); K.resize(n); C.resize(n); FOR(i, 0, n) { scanf("%d %d %d", &P[i], &K[i], &C[i]); PS.insert(P[i]); PS.insert(K[i]); task_sum += C[i]; } // Init basic data in FLOW graph FLOW_N = n + (PS.size() - 1) + 2; FLOW_S = FLOW_N - 2; FLOW_T = FLOW_N - 1; FOR(i, 0, FLOW_N) memset(FLOW_EDGE[i], 0, FLOW_N); memset(FLOW_LABEL, 0, FLOW_N); memset(FLOW_EXCESS, 0, FLOW_N); memset(FLOW_CUR, 0, FLOW_N); memset(FLOW_INQ, false, FLOW_N); FOR(i, 0, n) FLOW_EDGE[FLOW_S][i] = C[i]; // Create period nodes int prev_point = -1, node_id = n - 1; FORE(it, PS){ int period_capacity = *it - prev_point; if (prev_point != -1) { FLOW_EDGE[node_id][FLOW_T] = period_capacity * m; FOR(i, 0, n) if (prev_point >= P[i] && *it <= K[i]) FLOW_EDGE[i][node_id] = period_capacity; } prev_point = *it; ++node_id; } // Calculate result if (compute_flow() >= task_sum) printf("TAK\n"); else printf("NIE\n"); } |