网络流

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 const int maxn = 1000+1000;
 11 const int N = 500+10;
 12 const int INF = 1000000000+10;
 13 struct Edge{
 14     int from, to, cap, flow;
 15     Edge(){}
 16     Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d) {}
 17 
 18 };
 19 vector<Edge> edges;
 20 vector<int> G[maxn];
 21 struct Dinic { // O(n^2m)
 22 
 23 
 24 
 25     int m, s, t;
 26     bool vis[maxn];
 27     int d[maxn];
 28     int cur[maxn];
 29     void init(){
 30         edges.clear();
 31         for (int i = 0; i < maxn; i++) G[i].clear();
 32     }
 33     void AddEdge(int from, int to, int cap) {
 34         edges.push_back(Edge(from, to, cap, 0));
 35         edges.push_back(Edge(to, from, 0, 0));
 36         m = edges.size();
 37         G[from].push_back(m-2);
 38         G[to].push_back(m-1);
 39     }
 40     bool BFS(){
 41         memset(vis, 0, sizeof(vis));
 42         queue<int> Q;
 43         Q.push(s);
 44         d[s] = 0;
 45         vis[s] = 1;
 46         while (!Q.empty()) {
 47             int x = Q.front(); Q.pop();
 48             for (int i = 0; i < (int)G[x].size(); i++) {
 49                 Edge& e = edges[G[x][i]];
 50                 if (!vis[e.to] && e.cap > e.flow) {
 51                     vis[e.to] = 1;
 52                     d[e.to] = d[x] + 1;
 53                     Q.push(e.to);
 54                 }
 55             }
 56         }
 57         return vis[t];
 58     }
 59 
 60     int DFS(int x,int a) {
 61         if (x == t || a == 0) return a;
 62         int flow = 0, f;
 63         for (int& i = cur[x]; i < (int)G[x].size(); i++) {
 64             Edge& e = edges[G[x][i]];
 65             if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 66                 e.flow += f;
 67                 edges[G[x][i]^1].flow -= f;
 68                 flow += f;
 69                 a -= f;
 70                 if (a == 0) break;
 71             }
 72         }
 73         return flow;
 74     }
 75     int Maxflow(int s,int t) {
 76         this->s = s; this->t = t;
 77         int flow = 0;
 78         while (BFS()) {
 79             memset(cur, 0, sizeof(cur));
 80             flow += DFS(s, INF);
 81         }
 82         return flow;
 83     }
 84 }Rabbit;
 85 int n, m;
 86 int pi[N],si[N],ei[N];
 87 int main(){
 88     int T, cas = 0;
 89     scanf("%d",&T);
 90     while (T--) {
 91         scanf("%d%d",&n,&m);
 92         int sum = 0, tmp = 0;
 93         for (int i = 0; i < n; i++) {
 94             scanf("%d%d%d",pi+i,si+i,ei+i);
 95             sum += pi[i];
 96             tmp = max(tmp, ei[i]);
 97         }
 98         Rabbit.init();
 99         int cnt = 2+n;
100         for (int i = 0; i < n; i++) {
101             Rabbit.AddEdge(0, 2+i, pi[i]);
102         }
103         for (int i = 0; i < n; i++) {
104             for (int j = si[i]; j <= ei[i]; j++) {
105                 Rabbit.AddEdge(2+i, 2+n+j, 1);
106             }
107         }
108         for (int i = 1; i <= tmp; i++) Rabbit.AddEdge(2+n+i, 1, m);
109         printf("Case %d: ",++cas);
110         if (Rabbit.Maxflow(0, 1) == sum) puts("Yes");
111         else puts("No");
112         puts("");
113     }
114     return 0;
115 }