题解 P4043 【[AHOI2014/JSOI2014]支线剧情】

· · 题解

博客链接

这题的建图方式可以类比洛谷P1251

我是由那个题才想到这么建的，由于每条边至少经过一次，我们又不清楚需要跑多少次，把边看成点，点与汇点相连，可是我们又不知道最大流应该是多少，直接这么连会发生错误。利用那道题的思想，每条边最少需要一次，那么就每条边看做两个点，点1和点2，点1有1的流量流向汇点，点2接受源点的1的流量，这是一个补流的过程。利用补流的过程和把边拆成两个点，我们就可以跑出来最大流是边数的最小费用。 这么做吧，比其他的做法跑的慢很多，但是还可以ac的，只是最慢一个点还需要832ms(不开O2)


int head[max_], xiann = 2;
struct kk {
    int to, next, flow, val;
    kk() {}
    kk(int to, int next, int flow, int val) :to(to), next(next), flow(flow), val(val) {}
}xian[max_ << 1];
il void add(int a, int b, int c, int d) {
    /*if (c) {
        cout << a << " " << b << " " << c << endl;
    }*/
    xian[xiann] = kk(b, head[a], c, d);
    head[a] = xiann;
    xiann++;
}
int cur[max_], dis[max_], N = 0, que[max_], L, R;
int S, T;
bool vis[max_];
bool spfa() {
    re int i, now, to;
    for (i = 0; i <= N; i++) {
        cur[i] = head[i]; dis[i] = inf; vis[i] = 0;
    }
    L = 1, R = 0;
    que[++R] = S; vis[S] = 1; dis[S] = 0;
    while (L <= R) {
        now = que[L]; L++; vis[now] = 0;
        for (i = head[now]; i; i = xian[i].next) {
            to = xian[i].to;
            if (xian[i].flow  && dis[to] > dis[now] + xian[i].val) {
                dis[to] = dis[now] + xian[i].val;
                if (!vis[to]) {
                    vis[to] = 1;
                    que[++R] = to;
                }
            }
        }
    }
    return dis[T] != inf;
}
int mincost, maxflow;
int dfs(int now, int flow) {
    if (!flow || now == T)return flow;
    re int  to, tot = 0, f;
    vis[now] = 1;
    for (int &i = cur[now]; i; i = xian[i].next) {
        to = xian[i].to;
        if (!vis[to] && xian[i].flow && dis[to] == dis[now] + xian[i].val && (f = dfs(to, min(flow - tot, xian[i].flow)))) {
            tot += f;
            xian[i].flow -= f; xian[i ^ 1].flow += f;
            mincost += f * xian[i].val;
            if (tot == flow)break;
        }
    }
    vis[now] = 0;
    return tot;
}
void dinic() {
    while (spfa()) {
        maxflow += dfs(S, inf);
    }
}
il void addEdge(int a, int b, int c, int d) {
    //cout << a << " "  << b <<" "<< c << endl;
    add(a, b, c, d);
    add(b, a, 0, -d);
}
vector<pair<int, int> > ask[700];
map<int, pair<int, int> >mp;
il void ini() {
    re int n = read(),i,j,num,cost,to,idn,xianid = 0,nowxianid = 0,a,b;
    pair<int, int> temp;
    idn = n;
    for(i = 1;i <= n;i++){
        num = read();
        for (j = 1; j <= num; j++) {
            to = read(); cost = read();
            ask[i].push_back(make_pair(to, cost));
            ++xianid;
            a = ++idn; b = ++idn;
            mp[xianid] = make_pair(a, b);
        }
    }
    S = 0; N = T = ++idn;
    addEdge(S, 1, inf, 0);
    for (i = 1; i <= n; i++) {
        for (auto pa : ask[i]) {
            nowxianid++; 
            temp = mp[nowxianid];
            addEdge(temp.first, temp.second, inf, 0);
            addEdge(temp.first, T, 1, 0);
            addEdge(S,temp.second, 1, 0);
            addEdge(temp.second, pa.first, inf, 0);
            addEdge(i, temp.first, inf, pa.second);
        }
    }
    dinic();
    cout << mincost;
}
signed main() {
    ini();
    return 0;
}