今天爆零了，roadblock是原题，结果还审错题了。。。
题解
第一题：把最短路上的边提出来，然后跑最大流直到跑不动；但这样写比较麻烦；
用最小费用最大流也可以过，比某些网络流还快，这东西也玄学；
#includeusing namespace std;const int maxn = 3010, maxm = 41000, inf = 1000000008;struct Netflow{ int tot,head[maxn],maxflow,S,T,minlen; int inq[maxn],pre[maxn],pree[maxn],dis[maxn]; struct edge{ int to,f,w,nxt; }G[maxm]; void init(int s, int t){ S = s, T = t; tot = 1; memset(head,0,sizeof(head)); maxflow = 0; minlen = inf; } void add(int u,int v,int f,int w){ G[++tot].nxt = head[u]; G[tot].to = v; G[tot].f = f; G[tot].w = w; head[u] = tot; G[++tot].nxt = head[v]; G[tot].to = u; G[tot].f = 0; G[tot].w = -w; head[v] = tot; } void SPFA(){ queue Q; for(int i = 0; i <= T; i++)dis[i] = inf; memset(inq,0,sizeof(inq)); Q.push(S); inq[S] = 1; dis[S] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = head[u]; i; i= G[i].nxt){ int v = G[i].to; if(G[i].f && dis[v] > dis[u] + G[i].w){ dis[v] = G[i].w + dis[u]; if(!inq[v]){ Q.push(v); inq[v] = 1; } } } } minlen = dis[T]; } bool spfa(){ queue Q; for(int i = 0; i <= T; i++)dis[i] = inf; memset(inq,0,sizeof(inq)); // memset(pre,0,sizeof(pre)); // memset(pree,0,sizeof(pree)); Q.push(S); inq[S] = 1; dis[S] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = head[u]; i; i= G[i].nxt){ int v = G[i].to; if(G[i].f && dis[v] > dis[u] + G[i].w){ dis[v] = G[i].w + dis[u]; pre[v] = u; pree[v] = i; if(!inq[v]){ Q.push(v); inq[v] = 1; } } } } return dis[T] == minlen; } void augment(){ while(spfa()){ int u = T, delta = inf; while(u != S){ delta = min(delta, G[pree[u]].f); u = pre[u]; } u = T; while(u != S){ G[pree[u]].f -= delta; G[pree[u]^1].f += delta; u = pre[u]; } maxflow += delta; } printf("%d\n",maxflow); }};int main(){ freopen("roadblock.in","r",stdin); freopen("roadblock.out","w",stdout); int T,n,m; scanf("%d",&T); while(T--){ Netflow Tr; scanf("%d%d",&n,&m); Tr.init(1,n); while(m--){ int u, v, w; scanf("%d%d%d",&u,&v,&w); Tr.add(u, v, w, 1); Tr.add(v, u, w, 1); } Tr.SPFA(); Tr.augment(); } return 0;}
第二题：
一道拓扑排序，我完全没看出来，在那里傻逼并查集了半天；
可以知道一条路径中间忽略的车站等级一定更低，但是暴力建边复杂度是(m*n)不能过；
所以就有了传说已久的线段树优化建边，学std写了一波，线段树从下往上建边，对于出现的一组要求我们就开一个新节点；
至于无向图的线段树建边还要稍稍麻烦些，要开两棵树，有空看看吧
#includeusing namespace std;const int M = 600005;int in[M], h[M], mark[M], dg[M], tot, idx, n, m, pos[M];struct edge{ int v, nxt;}G[M * 10];void add(int u, int v){ G[++tot].nxt = h[u]; G[tot].v = v; h[u] = tot; in[v]++;}struct Node { Node *ls , *rs; int id;}pool[M << 1], *root, *tail = pool;Node * build(int l = 1, int r = n){ Node * nd = ++tail; nd->id = ++idx; if(l == r) mark[idx] = 1, pos[l] = idx; else { int mid = (l + r) >> 1; nd->ls = build(l, mid); add(nd->ls->id, nd->id); nd->rs = build(mid + 1, r); add(nd->rs->id, nd->id); } return nd;}#define Ls nd->ls, l, mid#define Rs nd->rs, mid+1, rvoid modify(int L, int R, int crtime, Node * nd = root, int l = 1, int r = n){ if(L <= l && r <= R){ add(nd->id, crtime); } else{ int mid = (l + r) >> 1; if(L <= mid)modify(L, R, crtime, Ls); if(R > mid)modify(L, R, crtime, Rs); }}void solve(){ int ans = 1; queue q; q.push(0); for(int i = 1; i <= n; i++) if(!in[pos[i]]) q.push(pos[i]), dg[pos[i]] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = h[u]; i; i = G[i].nxt){ int v = G[i].v; in[v]--; dg[v] = max(dg[v], dg[u] + mark[v]); if(!in[v])q.push(v); ans = max(ans, dg[v]); } //for(int i = 1; i <= n; i++)printf("%d ", dg[pos[i]]);puts(""); } printf("%d\n", ans);}int main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); scanf("%d%d", &n, &m); root = build(); int siz, lst, now; for(int i = 1; i <= m; i++){ scanf("%d%d", &siz, &lst); add(0, ++idx); add(idx, pos[lst]); for(int j = 2; j <= siz; j++){ scanf("%d", &now); add(idx, pos[now]); modify(lst+1, now-1, idx); lst = now; } } solve();}
第三题：一道巨复杂的费用流，又颓了没听，以下是std
//2s 512M#define PN "trouble"#include#include #include template inline void readin(T &res) { static char ch;T flag = 1; while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1; res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48; res*=flag;}template inline T abs(T a) { return a >= 0? a: -a;}template inline T max(T a,T b) { return a >= b? a: b;}template inline T min(T a,T b) { return a <= b? a: b;}const int N = 40 + 10;const int INF = 0x3f3f3f3f;const int NODES = 10 * N * N;const int EDGES = 100 * N * N;struct EDGE { int v, res, cost, upre;} g[EDGES];int head[NODES], ne = 1;inline void adde(int u,int v,int cap,int cost) { g[++ne] = (EDGE){v,cap,cost,head[u]};head[u] = ne; g[++ne] = (EDGE){u,0,-cost,head[v]};head[v] = ne;}int s, t;int flow, cost;#include std::queue q;int d[NODES], a[NODES], p[NODES];bool inq[NODES];bool SPFA() { while(!q.empty()) q.pop(); memset(d,63,sizeof(int)*(t+1)); memset(inq,false,sizeof(int)*(t+1)); d[s] = 0;inq[s] = true;q.push(s); a[s] = INF; int u, i, v; while(!q.empty()) { u = q.front();q.pop();inq[u] = false; for( i = head[u]; i; i = g[i].upre ) if(g[i].res && d[v = g[i].v] > d[u] + g[i].cost) { d[v] = d[u] + g[i].cost; if(!inq[v]) inq[v] = true, q.push(v); p[v] = i;a[v] = min(a[u],g[i].res); } } if(d[t] == INF) return false; flow += a[t];cost += a[t] * d[t]; for( u = t; u != s; g[p[u]].res -= a[t], g[p[u]^1].res += a[t], u = g[p[u]^1].v ); return true;}int T, n, m, A, B, t2, Q;bool Ball[N][N];inline int HOLE(int x,int y,int z) { return 3 * (x * m + y) + z + 1;}int main() { freopen(PN".in","r",stdin); freopen(PN".out","w",stdout); readin(T);//T=8~12 ans>0 print 1 readin(n);readin(m);readin(A);readin(B); s = 0;t = 3 * n * m + 2; memset(head,0,sizeof(int)*(t+1));ne = 1; t2 = 3 * n * m + 1;adde(t2,t,0,0); for( int i = 0, j; i < n; i++ ) for( j = 0; j < m; j++ ) { scanf("%1d",&Ball[i][j]);Ball[i][j] ^= 1; if((i+j)&1) { adde(s,HOLE(i,j,0),1,0); adde(s,HOLE(i,j,0),1,A); adde(s,HOLE(i,j,0),1,2*A); adde(s,HOLE(i,j,0),1,3*A); adde(HOLE(i,j,0),HOLE(i,j,1),1,0); adde(HOLE(i,j,0),HOLE(i,j,1),1,B-A); adde(HOLE(i,j,0),HOLE(i,j,2),1,0); adde(HOLE(i,j,0),HOLE(i,j,2),1,B-A); } else { adde(HOLE(i,j,0),t2,1,0); adde(HOLE(i,j,0),t2,1,A); adde(HOLE(i,j,0),t2,1,2*A); adde(HOLE(i,j,0),t2,1,3*A); adde(HOLE(i,j,1),HOLE(i,j,0),1,0); adde(HOLE(i,j,1),HOLE(i,j,0),1,B-A); adde(HOLE(i,j,2),HOLE(i,j,0),1,0); adde(HOLE(i,j,2),HOLE(i,j,0),1,B-A); } } for( int i = 0, j; i < n; i++ ) for( j = 0; j < m; j++ ) if(((i+j)&1) && Ball[i][j]) { if(j != 0 && Ball[i][j-1]) adde(HOLE(i,j,1),HOLE(i,j-1,1),1,0); if(j != m - 1 && Ball[i][j+1]) adde(HOLE(i,j,1),HOLE(i,j+1,1),1,0); if(i != 0 && Ball[i-1][j]) adde(HOLE(i,j,2),HOLE(i-1,j,2),1,0); if(i != n - 1 && Ball[i+1][j]) adde(HOLE(i,j,2),HOLE(i+1,j,2),1,0); } readin(Q); for( int x = 1, i; x <= Q; x++ ) { for( i = head[t2]; i; i = g[i].upre ) if(g[i].v == t) g[i].res++; while(SPFA()); printf("%d\n",8 <= T && T <= 12?cost > 0:cost); } return 0;}