HDU

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3572
  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn = 1e5 + 10;
  6 const int inf = 0x3f3f3f3f;
  7 
  8 int head[maxn * 2], depth[maxn * 2], cur[maxn * 2];
  9 int ans, t, n, m, s, x, y, z, mx, k, sum, q, cnt = 1;
 10 
 11 struct st
 12 {
 13     int to, next, w;
 14 }e[maxn * 2];
 15 
 16 inline void add(int u, int v, int w)
 17 {
 18     e[++cnt].to = v;
 19     e[cnt].next = head[u];
 20     e[cnt].w = w;
 21     head[u] = cnt;
 22 }
 23 
 24 inline int dfs(int u, int flow)
 25 {
 26     if(u == t) return flow;
 27     int ret = 0;
 28     for(int &i = cur[u]; i; i = e[i].next) // 弧优化
 29     {
 30         int v = e[i].to;
 31         if(depth[v] == depth[u] + 1 && e[i].w)
 32         {
 33             int di = dfs(v, min(e[i].w, flow - ret)); // 多路增广优化
 34             ret += di; e[i].w -= di; e[i ^ 1].w += di;
 35             if(flow - ret == 0) break;
 36         }
 37         
 38     }
 39     
 40     if(!ret) depth[u] = -1; // 炸点优化
 41     return ret;
 42 }
 43 
 44 int bfs() // 分层
 45 {
 46     queue<int> q;
 47     q.push(s);
 48     memset(depth, 0, sizeof(depth));
 49     depth[s] = 1;
 50     
 51     while(!q.empty())
 52     {
 53         int u = q.front(); q.pop();
 54         for(int i = head[u]; i; i = e[i].next)
 55         {
 56             int v = e[i].to;
 57             if(!depth[v] && e[i].w)
 58             {
 59                 depth[v] = depth[u] + 1;
 60                 q.push(v);
 61             }
 62             
 63         }
 64         
 65     }
 66     
 67     return depth[t];
 68 }
 69 
 70 int dinic()
 71 {
 72     int ans = 0;
 73     while(bfs())
 74     {
 75         for(int i = 0; i <= cnt; ++i) cur[i] = head[i];
 76         ans += dfs(s, inf);
 77     }
 78     
 79     return ans;
 80 }
 81 
 82 int main()
 83 {
 84     scanf("%d", &q);
 85     while(q--)
 86     {
 87         k++;
 88         scanf("%d %d", &n, &m);
 89         memset(e, 0, sizeof(e));
 90         memset(head, 0, sizeof(head));
 91         
 92         cnt = 1;
 93         s = 0; mx = -inf; sum = 0;
 94         
 95         for(int i = 1; i <= n; ++i)
 96         {
 97             scanf("%d %d %d", &x, &y, &z);
 98             sum += x;
 99             add(s, i, x), add(i, s, 0);
100             for(int j = y; j <= z; ++j)
101             {
102                 add(i, j + n, 1), add(j + n, i, 0);
103                 mx = max(mx, z);
104             }
105             
106         }
107         
108         t = mx + 1;
109         for(int i = 1; i <= mx; ++i)
110         {
111             add(i + n, t, m), add(t, i + n, 0);
112         }
113         
114         ans = dinic();
115         if(ans == sum) printf("Case %d: Yes
", k);
116         else printf("Case %d: No
", k);
117         
118         cout<<endl;
119     }
120     
121     return 0;
122 }
for(int &i = cur[u]; i; i = e[i].next)
{
和
for(int i = cur[u]; i; i = e[i].next)
{
cur[u] = i;
效果是一样的，去掉&也不能说错因为cur本来和head就是一样的，去掉就失去了优化的效果了