重新发一下,刚刚发现我的当前弧优化写的是假的。
但是还是TLE没有什么区别 前面AC的点都是0ms,后面6个点TLE。。。
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
read(t); read(args...);
}
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (B); I >= (A); --I)
const int maxv = 5e5 + 100;
const int maxe = 4e6 + 100;
typedef int arrTv[maxv];
typedef int arrTe[maxe << 1];
arrTv head, height, curr;
arrTe v, cap, flow, next;
int n, m, s, t, V, tot = -1;
inline void ae(int x, int y, int c) {
v[++tot] = y;
cap[tot] = c;
next[tot] = head[x];
head[x] = tot;
}
inline void ad(int x, int y, int c) {
ae(x, y, c);
ae(y, x, 0);
}
inline bool bfs() {
rep(i, 1, V) height[i] = 0;
height[s] = 1;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; ~i; i = next[i])
if (cap[i] > flow[i] && !height[v[i]]) {
height[v[i]] = height[x] + 1;
q.push(v[i]);
}
}
return height[t];
}
int dfs(int x, int cf) {
if (x == t || !cf) return cf;
int xys = 0;
for (int i = curr[x]; ~i; i = next[i], curr[x] = i)
if (cap[i] > flow[i] && height[v[i]] == height[x] + 1) {
int nf = dfs(v[i], std::min(cf, cap[i] - flow[i]));
if (nf) {
flow[i] += nf;
flow[i ^ 1] -= nf;
cf -= nf;
xys += nf;
}
}
if (!xys)
height[x] = -1;
return xys;
}
inline int maxflow() {
int ans = 0;
while (bfs()) {
rep(i, 1, V) curr[i] = head[i];
ans += dfs(s, INT_MAX);
}
return ans;
}
int main() {
int sum = 0;
read(n, m);
s = n + m + 1;
t = V = s + 1;
rep(i, 1, V) head[i] = -1;
rep(i, 1, n) {
int profit, process;
read(profit, process);
sum += profit;
ad(s, i, profit);
rep(j, 1, process) {
int machine, fee;
read(machine, fee);
ad(i, machine + n, fee);
}
}
rep(i, 1, m) {
int fee;
read(fee);
ad(i + n, t, fee);
}
int mf = maxflow();
printf("%d\n", sum - mf);
return 0;
}
```
by GKxx @ 2018-07-19 09:56:43