Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
55172 wzj33300 网络流 (flow) C++ 通过 100 151 MS 15924 KB 1413 2022-08-09 15:53:22

Tests(10/10):


#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 10; int n, m, x, y, w, cnt, col[maxn], dis[maxn], vis[maxn], d[maxn], head[maxn]; struct node { int nxt, to, val; } e[maxn << 1]; void add(int x, int y, int w) { e[++cnt].to = y; e[cnt].nxt = head[x]; head[x] = cnt; e[cnt].val = w; } queue<int> q; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &x, &y, &w); add(y, x, w); } if (n == 1) { printf("0\n0\n"); return 0; } memset(col, -1, sizeof(col)); q.push(n); vis[n] = 0; while (q.size()) { int x = q.front(); q.pop(); if (x == 1) { break; } for (int i = head[x]; i; i = e[i].nxt) { int v = e[i].to; if (vis[v]) continue; if (col[v] == -1 || col[v] == e[i].val ^ 1) { col[v] = e[i].val ^ 1; } else { // 有两种颜色 q.push(v); d[v] = d[x] + 1; vis[v] = 1; } } } if (d[1]) { printf("%d\n", d[1]); } else { printf("-1\n"); } for (int i = 1; i <= n; ++i) { if (col[i] == -1) { printf("0"); } else { printf("%d", col[i]); } } return 0; }


测评信息: