传送门
这题主要是先掌握欧拉通路的概念，然后是如何判断图是不是存在欧拉通路。
欧拉通路：通过图中每条边且只通过1次，并且经过每顶点的通路。
欧拉回路：通过图中每条边且只通过1次，并且经过每顶点的回路。
无向图：
欧拉通路：连通图＋只存在0个或两个度数为奇数的点。
欧拉回路：连通图＋所有节点的度数均为偶数。
有向图：
欧拉通路：连通图＋（所有点的入度＝出度 || 出两个点以外其他点的入度＝出度，1个点的入度－出度＝1，1个点的出度－入度＝1）。
ii e[500*500];
int in[510], out[510];//indegree,outdegree
int f[510];//判断是不是连通
int find(int x) {
return f[x] == -1 ? x : f[x] = find(f[x]);
}
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for (int i = 0;i < m;++i)
scanf("%d%d", &e[i].first, &e[i].second);
memset(in, 0,sizeof in);
memset(out, 0,sizeof out);
memset(f, -1,sizeof f);
int cnt = 0;
for (int i = 0;i < m;++i) {
in[e[i].first]++;
in[e[i].second]++;
int t1 = find(e[i].first);
int t2 = find(e[i].second);
if (t1 != t2) f[t1] = t2;
}
int o=0;
for (int i = 1;i <= n;++i) {
find(i);
if (f[i] == -1) o++;
}//o == 说明图连通
for (int i = 1;i <= n;++i)
if (in[i] & 1) cnt++;
if (cnt == 0 || cnt == 2) {
if (o == 1) printf("Yes");
else printf("No");
}else printf("No");
printf(" ");
memset(in, 0,sizeof in);
memset(f, -1,sizeof f);
cnt = 0;
for (int i = 0;i < m;++i) {
out[e[i].first]++;
in[e[i].second]++;
}
if (o > 1) puts("No");
else {
vector<int> vec;
for (int i = 1;i <= n;++i) {
if (in[i] != out[i]) vec.push_back(i);
}
if (vec.size() != 2 && vec.size() != 0) puts("No");
else {
if (vec.size() == 0) {
puts("Yes");
continue;
}
int u = vec[0], v = vec[1];
if (in[u] - out[u] == 1 && in[v] - out[v] == -1) puts("Yes");
else if (in[u] - out[u] == -1 && in[v] - out[v] == 1) puts("Yes");
else puts("No");
}
}
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}判断给出的图是不是合法。
4*4的格子中，每一个位置会出现指定的某些数字，但是由于覆盖的作用，只会看见最上面的1个，其他的被压在了下面。A覆盖了B，B覆盖了A，这样是明显不成立的，这题就是判断是不是会出现相互覆盖的情况，拓普排序。
ps:初始化的表要仔细打。。。
vector<int> have[5][5];
int a[5][5];
int in[10];
vector<int> G[10];
void init() {
have[1][1].push_back(1);
have[1][2].push_back(1), have[1][2].push_back(2);
have[1][3].push_back(2), have[1][3].push_back(3);
have[1][4].push_back(3);
have[2][1].push_back(1), have[2][1].push_back(4);
have[2][2].push_back(1), have[2][2].push_back(2), have[2][2].push_back(4), have[2][2].push_back(5);
have[2][3].push_back(2), have[2][3].push_back(3), have[2][3].push_back(5), have[2][3].push_back(6);
have[2][4].push_back(3), have[2][4].push_back(6);
have[3][1].push_back(4), have[3][1].push_back(7);
have[3][2].push_back(4), have[3][2].push_back(5), have[3][2].push_back(7), have[3][2].push_back(8);
have[3][3].push_back(5), have[3][3].push_back(6), have[3][3].push_back(8), have[3][3].push_back(9);
have[3][4].push_back(6), have[3][4].push_back(9);
have[4][1].push_back(7);
have[4][2].push_back(7), have[4][2].push_back(8);
have[4][3].push_back(8), have[4][3].push_back(9);
have[4][4].push_back(9);
}
void done(int u,int i, int j) {
for (int k = 0;k < have[i][j].size();++k) {
int v = have[i][j][k];
if (u == v) continue;
G[u].push_back(v);
in[v]++;
}
}
void getmap() {
for (int i = 1;i <= 9;++i) {
G[i].clear();
in[i] = 0;
}
for (int i = 1;i <= 4;++i) {
for (int j = 1;j <= 4;++j)
done(a[i][j], i, j);
}
}
void solve() {
getmap();
queue<int> que;
for (int i = 1;i <= 9;++i) {
if (in[i] == 0) {
que.push(i);
}
}
while(!que.empty()) {
int u = que.front();
que.pop();
for (int i = 0;i < G[u].size();++i) {
int v = G[u][i];
if (--in[v] == 0) {
que.push(v);
}
}
}
bool ok = true;
for (int i = 1;i <= 9;++i)
if (in[i] > 0) ok = false;
if (ok) puts("Lucky dog!");
else puts("BOOM!");
}
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
init();
int T;
cin >> T;
while(T--) {
for (int i = 1;i <= 4;++i) {
for (int j = 1;j <= 4;++j)
scanf("%d", &a[i][j]);
}
solve();
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}略
首先用补图还是很容易想到的（毕竟正着弄相对复杂了）。建立补图以后很容易就想到了2分图染色，最后判断是不是成立。
const int maxn = 5e2 + 10;
int n, m;
int col[maxn];
vector<int> G[maxn];
int g[maxn][maxn];
bool dfs(int u,int color) {
col[u] = color;
for (int i = 0;i < G[u].size();++i) {
int v = G[u][i];
if (col[u] == col[v]) return false;
if (!col[v] && !dfs(v, -color)) return false;
}
return true;
}
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
int t;
cin >> t;
while(t--) {
scanf("%d%d", &n, &m);
memset(g, 0,sizeof g);
int u, v;
for (int i = 1;i <= m;++i) {
scanf("%d%d", &u, &v);
g[u][v] = g[v][u] = 1;
}
for (int i = 1;i <= n;++i) {
G[i].clear();
for (int j = 1;j <= n;++j)
if (i != j && !g[i][j]) G[i].push_back(j);
}
bool yes = true;
memset(col, 0,sizeof col);
for (int i = 1;i <= n;++i) {
if (!col[i] && G[i].size() && !dfs(i, 1)) {
yes=false;
}
}
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= n;++j) {
if (i == j) continue;
if (g[i][j] && col[i]*col[j]<0)yes=false;
if (!g[i][j] && col[i]*col[j]>=0)yes=false;
}
}
if (yes) puts("Yes");
else puts("No");
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}好懂，可能就“使得任意两人走过的距离加上2人所在食堂的距离的最大值最小”这句话需要解释下。任意两个人A, B 如果在同1个食堂的话就是他两个走过的距离和，如果不在同1个食堂就再加上两个食堂之间的距离。
求最大最小，明显2分结果值。然后根据2分值建图判断可行性。
我们可以用bool值表示每一个人的选择。对第i个人而言，i表示其选择第1食堂，i+N表示其选择2食堂。
<1> 相互仇恨的两个人x,y
必定建立4条边(x,y+N), (y,x+N),(x+N,y),(y+N,x)。表示两个选择不同的食堂。
<2> 相互喜欢的两个人x,y
必定建立4条边(x,y),(y,x),(x+N,y+N),(y+N,x+N)表示两个人选择同1个食堂。
<3> 对人意的两个人x,y
这里就看代码了。。。
/*****************************************
Author :Crazy_AC(JamesQi)
Time :2016
File Name :
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \| |// `.
/ \||| : |||// \
/ _||||| -:- |||||- \
| | \\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
#define MEM(x,y) memset(x, y,sizeof x)
#define pk push_back
#define lson rt << 1
#define rson rt << 1 | 1
#define bug cout << "BUG HERE\n"
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
const double eps = 1e⑻;
const double pi = 4 * atan(1);
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int nCase = 0;
int dcmp(double x){//精度正负、0的判断
if (fabs(x) < eps) return 0;
return x < 0?-1:1;
}
inline int read(){
char c = getchar();
while (!isdigit(c)) c = getchar();
int x = 0;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
const int maxn = 2010;
struct Edge{
int to, nxt;
Edge() {}
Edge(int to,int nxt) {
this->to = to;
this->nxt = nxt;
}
}edges[maxn*maxn];
int N, A, B;
int head[maxn], ecnt;
void add(int u,int v) {
edges[ecnt] = Edge(v, head[u]), head[u] = ecnt++;
}
int dfn[maxn], low[maxn], depth;
bool in[maxn];
stack<int> st;
int belong[maxn];
int block;
void tarjan(int u) {
dfn[u] = low[u] = ++depth;
in[u] = true;
st.push(u);
for (int i = head[u]; ~i;i = edges[i].nxt) {
int v = edges[i].to;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
}else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
block++;
while(true) {
int x = st.top();
st.pop();
in[x] = false;
belong[x] = block;
if (x == u) break;
}
}
}
struct point {
int x, y;
void read() {
scanf("%d%d", &x, &y);
}
}p[maxn], hate[maxn], like[maxn], s1, s2;
int dis[maxn][maxn];
inline int dist(point& a,point& b) {//曼哈顿距离
return abs(a.x - b.x) + abs(a.y - b.y);
}
bool ok() {
depth = block = 0;
memset(dfn, -1,sizeof dfn);
for (int i = 1;i <= 2*N;++i)
if (dfn[i] == -1) tarjan(i);
for (int i = 1;i <= N;++i)
if (belong[i] == belong[i+N]) return false;
return true;
}
void getmap(int limit) {
ecnt = 0;
memset(head, -1,sizeof head);
for (int i = 1;i <= A;++i) {
add(hate[i].x, hate[i].y + N);
add(hate[i].y, hate[i].x + N);
add(hate[i].x + N, hate[i].y);
add(hate[i].y + N, hate[i].x);
}
for (int i = 1;i <= B;++i) {
add(like[i].x, like[i].y);
add(like[i].y, like[i].x);
add(like[i].x + N, like[i].y + N);
add(like[i].y + N, like[i].x + N);
}
for (int i = 1;i <= N;++i) {
for (int j = i + 1;j <= N;++j) {
if (dis[i][N+1] + dis[j][N+1] > limit) {//不能1同食堂
add(i, j + N);
add(j, i + N);
}
if (dis[i][N+2] + dis[j][N+2] > limit) {
add(i + N, j);
add(j + N, i);
}
if (dis[i][N+1] + dis[j][N+2] + dis[N+1][N+2] > limit) {
add(i, j);
add(j+N, i+N);
}
if (dis[i][N+2] + dis[j][N+1] + dis[N+1][N+2] > limit) {
add(i+N,j+N);
add(j, i);
}
}
}
}
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
int T_T;
scanf("%d", &T_T);
while(T_T--) {
scanf("%d%d%d", &N, &A, &B);
s1.read(), s2.read();
dis[N+1][N+2] = dist(s1, s2);
for (int i = 1;i <= N;++i)
{
p[i].read();
dis[i][N+1] = dist(p[i], s1);
dis[i][N+2] = dist(p[i], s2);
}
for (int i = 1;i <= A;++i)
hate[i].read();
for (int i = 1;i <= B;++i)
like[i].read();
int low = 0, high = 50000000;
int ans = -1;
while(low <= high) {
int mid = (low + high) / 2;
getmap(mid);
if (ok()) {
ans = mid;
high = mid - 1;
}else low = mid + 1;
}
printf("%d\n", ans);
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}略
套路，缩点＋匹配
const int N = 5000 + 10;
const int M = 100000 + 10;
int n, m;
int head[N], pnt[M], nxt[M], cnt;
void init() {
memset(head, -1,sizeof head);
cnt = 0;
}
void addedge(int u,int v) {
pnt[cnt] = v, nxt[cnt] = head[u],head[u] = cnt++;
}
int dfn[N], low[N], belong[N];
int Times;
stack<int> st;
int scc;
void Tarjan(int u) {
dfn[u] = low[u] = ++Times;
st.push(u);
for (int i = head[u];~i;i = nxt[i]) {
int v = pnt[i];
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if (!belong[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scc;
while(true) {
int x = st.top();
st.pop();
belong[x] = scc;
if (x == u) break;
}
}
}
vector<int> G[N];
int linker[N];
bool vis[N];
bool dfs(int u) {
for (int i = 0;i < G[u].size();++i) {
int v = G[u][i];
if (vis[v]) continue;
vis[v] = true;
if (linker[v] == -1 || dfs(linker[v])) {
linker[v] = u;
return true;
}
}
return false;
}
int Hungary(){
int ans = 0;
memset(linker, -1,sizeof linker);
for (int i = 1;i <= scc;++i) {
memset(vis, false,sizeof vis);
if (dfs(i)) ans++;
}
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
init();
int u, v;
for (int i = 1;i <= m;++i) {
scanf("%d%d",&u,&v);
addedge(u, v);
}
memset(dfn, 0,sizeof dfn);
memset(belong, 0,sizeof belong);
scc = Times = 0;
for (int i = 1;i <= n;++i) G[i].clear();
for (int i = 1;i <= n;++i) if (!dfn[i]) Tarjan(i);
for (int i = 1;i <= n;++i) {
for (int j = head[i];~j;j = nxt[j]) {
int v = pnt[j];
if (belong[i] != belong[v]) {
G[belong[i]].push_back(belong[v]);
}
}
}
printf("%d\n", scc - Hungary());
}
return 0;
}求所有环中的最大边权的最小值。
可以两种做法。
1.2分结果然后scc.
2.最小生成树的利用.
说第2种吧。。。把边排序，然后合并第1个构成的环的最后1天边就是答案。
const int maxn = 5e5 + 10;
const int maxm = 2e6 + 10;
struct Edge {
int u, v, c;
Edge() {}
Edge(int u,int v,int c) {
this->u = u;
this->v = v;
this->c = c;
}
bool operator < (const Edge& rhs) const {
return c < rhs.c;
}
void read() {
scanf("%d%d%d", &u, &v, &c);
}
}e[maxm];
int f[maxn];
int find(int x) {
return f[x] == -1?x : f[x] = find(f[x]);
}
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
int n , m;
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for (int i = 0;i < m;++i)
e[i].read();
sort(e,e+m);
memset(f, -1,sizeof f);
int ans = -1;
for (int i = 0;i < m;++i) {
int t1 = find(e[i].u);
int t2 = find(e[i].v);
if (t1 != t2) {
f[t1] = t2;
}else if (ans == -1) ans = e[i].c;
}
if (ans == -1) puts("No solution!");
else printf("%d\n", ans);
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}略
问的是最短路的条数，且任意两条路不重复。首先每条路径都是最短的，所以就建立最短路树。然后就是最大流算法了。并附上最大流模版。。。
const int maxn = 1010;
vector<ii> G[2][maxn];//v, cost
int n, m;
int dis1[maxn], dis2[maxn], in[maxn];
void spfa(int s,int t,int* d, int o) {
for (int i = 1;i <= n;++i)
d[i] = INF;
memset(in, 0,sizeof in);
d[s] = 0;
queue<int> que;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
in[u] = 0;
for (int i = 0;i < G[o][u].size();++i) {
int v = G[o][u][i].first;
int cost = G[o][u][i].second;
if (d[v] > d[u] + cost) {
d[v] = d[u] + cost;
if (in[v] == 0) {
in[v] = 1;
que.push(v);
}
}
}
}
}
struct Edge{
int from, to, cap, flow;
Edge(){}
Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
struct ISAP{
int p[maxn], num[maxn], cur[maxn], d[maxn];
int s, t, n, m;
bool vis[maxn];
vector<int> G[maxn];
vector<Edge> edges;
void init(int n) {
this->n = n;
for (int i = 0;i <= n;++i) {
G[i].clear();
d[i] = INF;
}
edges.clear();
}
void addedge(int from,int to,int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool bfs() {
memset(vis, false,sizeof vis);
queue<int> que;
d[t] = 0;
vis[t] = true;
que.push(t);
while(!que.empty()) {
int u = que.front();
que.pop();
for (int i = 0;i < G[u].size();++i) {
Edge& e = edges[G[u][i]^1];
if (e.cap > e.flow && !vis[e.from]) {
vis[e.from] = true;
d[e.from] = d[u] + 1;
que.push(e.from);
}
}
}
return vis[s];
}
int Augment() {
int u = t, flow = INF;
while(u != s) {
Edge& e = edges[p[u]];
flow = min(flow, e.cap - e.flow);
u = edges[p[u]].from;
}
u = t;
while(u != s) {
edges[p[u]].flow += flow;
edges[p[u]^1].flow -= flow;
u = edges[p[u]].from;
}
return flow;
}
int MaxFlow(int s,int t) {
this->s = s,this->t = t;
int ret = 0;
bfs();
if (d[s] >= n) return 0;
memset(num, 0,sizeof num);
memset(cur, 0,sizeof cur);
for (int i = 0;i < n;++i) {
if (d[i] < INF) num[d[i]]++;
}
int u = s;
while(d[s] < n) {
if (u == t) {
ret += Augment();
u = s;
}
bool ok = false;
for (int i = cur[u];i < G[u].size();++i) {
Edge& e = edges[G[u][i]];
if (e.cap > e.flow && d[u] == d[e.to] + 1) {
ok = true;
p[e.to] = G[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if (!ok) {
int Min = n - 1;
for (int i = 0;i < G[u].size();++i) {
Edge& e = edges[G[u][i]];
if (e.cap > e.flow) Min = min(Min, d[e.to]);
}
if (--num[d[u]] == 0) break;
num[d[u] = Min + 1]++;
cur[u] = 0;
if (u != s) u = edges[p[u]].from;
}
}
return ret;
}
}solve;
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// clock_t _ = clock();
int t;
cin >> t;
while(t--) {
scanf("%d%d", &n, &m);
for (int i = 1;i <= n;++i)
G[0][i].clear(), G[1][i].clear();
int u, v, c;
for (int i = 1;i <= m;++i) {
scanf("%d%d%d", &u, &v, &c);
G[0][u].push_back(ii(v, c));
G[1][v].push_back(ii(u, c));
}
int st, ed;
scanf("%d%d", &st, &ed);
spfa(st, ed, dis1, 0);
spfa(ed, st, dis2, 1);
int limit = dis1[ed];
if (limit == INF) {
printf("%d\n", 0);
continue;
}
solve.init(n);
for (int i = 1;i <= n;++i) {
for (int j = 0;j < G[0][i].size();++j) {
int k = G[0][i][j].first;
if (dis1[i] != INF && dis2[k] != INF && dis1[i] + dis2[k] + G[0][i][j].second == limit) {
solve.addedge(i, k, 1);
}
}
}
int ans = solve.MaxFlow(st, ed);
printf("%d\n", ans);
}
// printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
return 0;
}从1号点到n号点在k的时间内逃出去的条件下，能带走的最大价值珠宝。
又是1种套路。2分答案，然后跑最短路，看能不能逃出去。
/*****************************************
Author :Crazy_AC(JamesQi)
Time :2016
File Name :
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \| |// `.
/ \||| : |||// \
/ _||||| -:- |||||- \
| | \\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
#define MEM(x,y) memset(x, y,sizeof x)
#define pk push_back
#define lson rt << 1
#define rson rt << 1 | 1
#define bug cout << "BUG HERE\n"
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
const double eps = 1e⑻;
const double pi = 4 * atan(1);
const long long inf = 1e20 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int nCase = 0;
int dcmp(double x){//精度正负、0的判断
if (fabs(x) < eps) return 0;
return x < 0?-1:1;
}
inline int read(){
char c = getchar();
while (!isdigit(c)) c = getchar();
int x = 0;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
const int maxn = 1e4 + 10;
struct Edge {
int v, limit, cost;
Edge() {}
Edge(int v,int limit, int cost) {
this->v = v;
this->limit = limit;
this->cost = cost;
}
};
vector<Edge> G[maxn];