为什么不可以只连从k==0的点到1容量无穷的边而是每个点都要连到1容量无穷的边
查看原帖
为什么不可以只连从k==0的点到1容量无穷的边而是每个点都要连到1容量无穷的边
587428
1577698530a楼主2023/2/19 11:28
for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        if (i>=2){
            add(i, 1, infinity2, 0);
        }
        while (k--) {
            int j, w;
            scanf("%d%d", &j, &w);
            c[i] --, c[j] ++,cost+=w;
            add_edge(i, j, infinity2, w), add_edge(j, i, 0, -w);
        }
    }
    //add(T, S, infinity2, 0);
    //S = 0, T = n + 2;
    for (int i = 1; i <= n; i++) {
        if (c[i] > 0)add(S, i, c[i], 0);
        else if(c[i]<0)add(i, T, -c[i], 0);
    }

这样建图可以过

for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        if (k==0){
            add(i, 1, infinity2, 0);
        }
        while (k--) {
            int j, w;
            scanf("%d%d", &j, &w);
            c[i] --, c[j] ++,cost+=w;
            add_edge(i, j, infinity2, w), add_edge(j, i, 0, -w);
        }
    }
    //add(T, S, infinity2, 0);
    //S = 0, T = n + 2;
    for (int i = 1; i <= n; i++) {
        if (c[i] > 0)add(S, i, c[i], 0);
        else if(c[i]<0)add(i, T, -c[i], 0);
    }

这样就不可以

2023/2/19 11:28
加载中...