滴滴编程笔试
选择题好搞啊， 这些看规律 我吐了。。 计算题挺多的 好评
第一题只过了36%，二分图和最大流都换了 。。我建图感觉也没错，求过了的大佬指点一下
const int N = 2000;
const int inf = 1e9;
int bol, n, m, st = N - 2, ed = N - 1;
int head[N], lv[N], vis[N][N], flag[N][N];
struct node {
int e, flow, nex;
node() {}
node(int e, int flow, int nex) : e(e), flow(flow), nex(nex) {}
} edg[N << 3];
inline void add(int s, int e, int flow) {
edg[bol] = node(e, flow, head[s]);
head[s] = bol++;
edg[bol] = node(s, 0, head[e]);
head[e] = bol++;
}
bool BFS() {
memset(lv, 0, sizeof lv);
lv[st] = 1;
queue<int>q;
q.push(st);
while(!q.empty()) {
int s = q.front();
q.pop();
if(s == ed)return true;
for(int i = head[s]; ~i; i = edg[i].nex) {
int e = edg[i].e;
if(!lv[e] && edg[i].flow)
lv[e] = lv[s] + 1, q.push(e);
}
}
return false;
}
int dfs(int s, int ff) {
if(!ff || s == ed) return ff;
int ans = 0;
for(int i = head[s]; ~i; i = edg[i].nex) {
int e = edg[i].e;
if(lv[e] == lv[s] + 1) {
int u = dfs(e, min(ff - ans, edg[i].flow));
ans += u;
edg[i].flow -= u;
edg[i ^ 1].flow += u;
if(ans == ff) return ans;
}
}
if(!ans) lv[s] = 0;
return ans;
}
int dinic() {
int ans = 0;
while(BFS()) ans += dfs(st, inf);
return ans;
}
int main () {
memset (head, -1, sizeof head);
int n, m;
cin >> n >> m;
while (m --) {
int a, b;
scanf ("%d %d", &a, &b);
flag[a][b + n] = 1;
}
for (int i = 1; i <= n; i++) {
add (st, i, 1);
add (i + n, ed, 1);
for (int j = n + 1; j <= n + n; j++) if (!flag[i][j] && i != j){
add (i, j, inf);
// cout << i << ' ' << j << endl;
}
}
cout << dinic () / 2 * 2 << endl;
return 0;
}
代码写的丑 不想贴了。。。
