69 条题解

  • 2
    @ 2017-07-08 22:05:01
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m,e;
    vector<int> f;
    vector<int> a;
    vector<int> e_x;
    vector<int> e_y;
    vector<int> e_v;
    vector<int> pre;
    vector<vector<int> > c;
    deque<int> q;
    
    int bfs_1(int s,int t)
    {
        f.resize(0);
        f.resize(n+2,0);
        f[s]=oo_max;
        pre.resize(0);
        pre.resize(n+2,-1);
        pre[s]=s;
        q.resize(0);
        for (q.push_back(s);(!q.empty())&&pre[t]==-1;q.pop_front())
        {
            int now=q.front();
            for (int i=1;i<=n+1;i++)
                if (c[now][i]&&pre[i]==-1)
                {
                    pre[i]=now;
                    f[i]=min(c[now][i],f[now]);
                    q.push_back(i);
                }
        }
        return ((pre[t]!=-1)?f[t]:-1);
    }
    
    int max_flow_1(int s,int t)
    {
        int temp=0,ans=0;
        while ((temp=bfs_1(s,t))!=-1)
        {
            for (int i=t;i!=s;i=pre[i])
                c[pre[i]][i]-=temp,c[i][pre[i]]+=temp;
            ans+=temp;
        }
        return ans;
    }
    
    int main()
    {
        while (~scanf("%d%d",&n,&e))
        {
            c.resize(0);
            c.resize(n+2);
            for (int i=1;i<=n+1;i++)
                c[i].resize(n+2,0);
            e_x.resize(0);
            e_x.resize(e+1,0);
            e_y.resize(0);
            e_y.resize(e+1,0);
            e_v.resize(0);
            e_v.resize(e+1,0);
            for (int i=1;i<=e;i++)
            {
                scanf("%d%d%d",&e_x[i],&e_y[i],&e_v[i]);
                c[e_x[i]][e_y[i]]=c[e_y[i]][e_x[i]]=e_v[i];
            }
            scanf("%d",&m);
            a.resize(0);
            a.resize(m+1,0);
            for (int i=1;i<=m;i++)
            {
                scanf("%d",&a[i]);
                c[a[i]][n+1]=oo_max;
            }
            printf("%d\n",max_flow_1(1,n+1));
        }
    }
    
  • 1
    @ 2017-04-26 21:54:43

    简单最大流,dinic解决

    #include <stdio.h>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    #include <iostream>
    #include <string>
    #include <map>
    #include <ciso646>
    #include <stack>
    #include <cstdlib>
    #include <vector>
    #include <cstdint>
    using namespace std;
    const int maxn = 1000001;
    
    struct edge
    {
        int v;
        int w;
        int next;
    }g[500001];
    queue<int> q;
    int head[100001], dis[100001], cur[100001];
    int n, m, i, j, k, l, tot=-1, ans, total,t,s;
    
    inline int read()
    {
        int ans = 0, f = 1;
        char c = getchar();
        while (!isdigit(c))
        {
            if (c == '-') f = -1;
            c = getchar();
        }
        while (isdigit(c))
        {
            ans = ans * 10 + c - 48;
            c = getchar();
        }
        return ans * f;
    }
    
    inline void addedge(int u, int v, int w)
    {
        ++tot;
        g[tot].v = v;
        g[tot].w = w;
        g[tot].next = head[u];
        head[u] = tot;
    }
    
    bool bfs()
    {
        while (!q.empty())
            q.pop();
        memset(dis, -1, sizeof(dis));
        dis[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (i = head[u];i != -1;i = g[i].next)
            {
                int v = g[i].v;
                if (dis[v] == -1 && g[i].w > 0)
                {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                    if (v == t) return true;
                }
            }
        }
        return false;
    }
    
    
    int dfs(int x,int flow)
    {
        if (x == t or (!flow))
            return flow;
        int w = 0;
        for (int i = cur[x];i != -1 && w < flow; i = g[i].next)
        {
            int v = g[i].v;
            if (dis[v] == dis[x] + 1 && g[i].w>0)
            {
                int delta = dfs(v, min(flow - w, g[i].w));
                g[i].w -= delta;
                g[i^1].w += delta;
                w += delta;
                if (g[i].w)
                    cur[x] = i;
            }
        }
        if (w < flow)
            dis[x] = -1;
        return w;
    }
    
    int main()
    {
        n = read();
        m = read();
        memset(head, -1, sizeof(head));
        s = 1;
        t = n + 1;
        
        for (int i = 1;i <= m;i++)
        {
            int u, v, w;
            u = read();
            v = read();
            w = read();
            addedge(u, v, w);
            addedge(v, u, w);
        }
        int e = read();
        for (i = 1;i <= e;i++)
        {
            int k;
            k = read();
            addedge(k, t, maxn);
        }
        while (bfs())
        {
            for (i = 0;i <= t;i++)
                cur[i] = head[i];
            int tans = dfs(s, maxn);
            ans += tans;
        }
        printf("%d\n", ans);
        system("pause");
        return 0;
    
    }
    
  • 1
    @ 2016-05-28 23:16:06

    感谢前辈!
    70的要注意!无向图最大流
    附上dinic算法代码:
    ```c++
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #define min(x,y) ((x<y)?(x):(y))
    using namespace std;
    const int Max=2147383647;
    int map[350][350];
    int n,m,c,tas,ans;
    int dis[350];
    int Bfs(){
    memset(dis,-1,sizeof(dis));
    int l=1,r=2,que[4000];
    dis[1]=0;
    que[1]=1;
    while(l<r){
    int p=que[l];
    for(int i=1;i<=n+1;i++)
    if(dis[i]<0&&map[p][i]>0){
    dis[i]=dis[p]+1;
    que[r]=i;
    r++;
    }
    l++;
    }
    if(dis[n+1]>0) return 1;
    return 0;

    }
    int find(int deep,int minflow){
    int mf=0;
    if(deep==n+1) return minflow;
    for(int i=1;i<=n+1;i++)
    if( dis[i]==dis[deep]+1
    && map[deep][i]>0
    &&(mf=find(i,min(map[deep][i],minflow)))){
    map[deep][i]-=mf;
    map[i][deep]+=mf;
    return mf;
    }
    return 0;
    }
    int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    int j,k,s;
    scanf("%d%d%d",&j,&k,&s);
    map[j][k]=s;
    map[k][j]=s; 添加了这一句就变成无向图,不过我又有个困惑:这会影响增广吗?
    }
    scanf("%d",&c);
    for(int i=1;i<=c;i++){
    int j;
    scanf("%d",&j);
    map[j][n+1]=Max;
    }
    while(Bfs()){
    while(tas=find(1,Max)){
    // printf("%d ",tas);
    ans+=tas;
    }
    }

    printf("%d\n",ans);
    return 0;
    }
    ```

  • 0
    @ 2016-12-26 23:11:12

    测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 580 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 604 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 604 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 608 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 604 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 604 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 644 KiB, score = 10
    Accepted, time = 30 ms, mem = 644 KiB, score = 100

    最大流 = 最小割定理

    代码
    ```c++
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<map>
    #include<cctype>
    #include<queue>
    #include<functional>
    #include<set>
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    #define Sy system("pause")
    using namespace std;
    const int maxn = 520;
    const int INF = 0x3f3f3f;
    #define For(a,b) for(int i = (a);i<(b);i+=1)
    #define Fore(a,b) for(int i = (a),i<=(b);i+=1)

    struct Dinic{
    struct Edge {
    int from, to, cap, flow;
    Edge(int a, int b, int c, int d) :from(a), to(b), cap(c), flow(d) {}
    Edge(){}
    friend bool operator < (const Edge& a, const Edge& b) {
    return a.from < b.from || (a.from == b.from && a.to < b.to);
    }
    };

    int n, m, s, t;
    vector<Edge> old;
    vector<Edge> edges;//边数两倍
    vector<int> G[maxn];
    bool vis[maxn]; // BFS使用
    int d[maxn];
    int cur[maxn];

    void init(int n){ For(0, n) G[i].clear(); edges.clear(); }

    void AddEdge(int from, int to, int cap, int flow){
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
    }

    bool BFS(){ //构建层次网络,如果构建的时候汇点没有访问过证明已经不在网络中
    Mem(vis, 0);
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while (!Q.empty()){
    int x = Q.front(); Q.pop();
    For(0, G[x].size()){
    Edge & e = edges[G[x][i]];
    if (!vis[e.to] && e.cap > e.flow){
    vis[e.to] = 1;
    d[e.to] = d[x] + 1;//层次
    Q.push(e.to);
    }
    }
    }
    return vis[t];
    }

    int DFS(int x, int a){
    if (x == t || a == 0) return a;//如果已经到汇点或者增量是0,没必要继续因为已经找到了最大流
    int flow = 0, f;
    for (int & i = cur[x]; i<G[x].size(); i += 1){
    Edge& e = edges[G[x][i]];
    //如果e.to是x的儿子结点并且其增量大于0
    if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){
    e.flow += f;
    edges[G[x][i] ^ 1].flow -= f;
    flow += f;
    a -= f;
    if (!a) break;
    }
    }
    return flow;
    }

    int MaxFlow(int s, int t){
    this->s = s; this->t = t;
    int flow = 0;
    while (BFS()){
    Mem(cur, 0);
    flow += DFS(s, INF);
    }
    return flow;
    }
    };

    int main(){
    Dinic D;
    int n, e;
    scanf("%d %d", &n, &e);
    D.init(n + 2);
    int a, b, c;
    For(0, e){
    scanf("%d %d %d", &a, &b, &c);
    D.AddEdge(a, b, c,0);
    D.AddEdge(b, a, c, 0);
    }
    int m, aa;
    scanf("%d", &m);
    For(0, m){
    scanf("%d", &aa);
    D.AddEdge(aa, n + 1, INF,0);
    }
    printf("%d\n", D.MaxFlow(1, n + 1));

    return 0;
    }
    ```

  • 0
    @ 2016-11-10 15:06:02

    这题在点 1~N 之间的边是双向的,不是双向的会有三个点过不了
    ```c++

    #include <iostream>
    #include <fstream>

    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    const int maxn = 505;
    const int INF = 0x7fffffff;

    struct Edge {
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
    };

    struct EdmondsKarp {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int a[maxn];
    int p[maxn];

    void init(int n) {
    for (int i = 0; i < n; ++i) G[i].clear();
    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)); // reverse edge
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
    }

    int Maxflow(int s, int t) {
    int flow = 0;
    for (;;) {
    memset(a, 0, sizeof(a));
    queue<int> Q;
    Q.push(s);
    a[s] = INF;
    while (!Q.empty()) {
    int x = Q.front(); Q.pop();
    for (int i = 0; i < G[x].size(); ++i) {
    Edge &e = edges[G[x][i]];
    if (!a[e.to] && e.cap > e.flow) {
    p[e.to] = G[x][i];
    a[e.to] = min(a[x], e.cap - e.flow);
    Q.push(e.to);
    }
    }
    if (a[t]) break;
    }
    if (!a[t]) break;
    for (int u = t; u != s; u = edges[p[u]].from) {
    edges[p[u]].flow += a[t];
    edges[p[u] ^ 1].flow -= a[t];
    }
    flow += a[t];
    }
    return flow;
    }
    };

    int main()
    {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif

    EdmondsKarp ek;
    int n, e; cin >> n >> e;
    ek.init(n+2);
    int a, b, w;
    for (int i = 0; i < e; ++i) {
    cin >> a >> b >> w;
    ek.AddEdge(a, b, w);
    ek.AddEdge(b, a, w);
    }
    int m; cin >> m;
    for (int i = 0; i < m; ++i) {
    cin >> a;
    ek.AddEdge(a, n+1, INF);
    }
    cout << ek.Maxflow(1, n+1) << endl;
    return 0;
    }

  • 0
    @ 2016-10-04 09:41:03

  • 0
    @ 2016-10-04 09:40:02

    用EK实现~

    c++
    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    int G[105][105];
    int n=0,m=0,ans=0,maa=0;
    bool findr()
    {
    int l[100000],r=0,f=1,p[202]={0};//p[i] is father of i
    l[r]=1;bool bj=true,bj2=false;;
    while(1)
    {
    if(r==f)
    {
    bj=true;
    break;
    }
    for(int i=1;i<=m;i++)
    {
    if(G[l[r]][i]>0&&p[i]==0)
    {
    l[f]=i;
    f++;
    p[i]=l[r];
    bj=false;
    if(i==m)
    bj2=true;
    }
    }
    if(bj2)
    {
    bj=false;
    break;
    }
    r++;
    }
    int minn=10000000,ii=m;
    if(!bj)
    {
    while(ii!=1)
    {
    if(G[p[ii]][ii]<minn)
    minn=G[p[ii]][ii];
    ii=p[ii];
    }
    ii=m;
    while(ii!=1)
    {
    G[p[ii]][ii]-=minn;
    G[ii][p[ii]]+=minn;
    ii=p[ii];
    }
    ans+=minn;
    return true;
    }
    else return false;
    }
    int main()
    {
    scanf("%d%d",&m,&n);
    int v,vv,nn;
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d%d",&v,&vv,&nn);
    G[v][vv]+=nn;
    G[vv][v]+=nn;
    }
    m++;
    scanf("%d",&maa);int hhd=0;
    for(int gga=0;gga<maa;gga++)
    {
    scanf("%d",&hhd);
    G[hhd][m]=2147482647;
    }
    while(findr()){}
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2016-06-21 20:59:33

    最大流最小割,注意无向双边。
    Dinic实现还是嫌长……
    ```c++
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int INF = 2147483647;
    const int maxn = 500;

    struct Ed
    {
    int from,to,cap,flow;
    Ed(int a=0,int b=0,int c=0,int d=0) : from(a),to(b),cap(c),flow(d) {}
    };

    int n,m,e,cur[maxn],d[maxn];
    vector<int> G[maxn];
    vector<Ed> edges;

    inline void add_edges(int from,int to,int cap)
    {
    edges.push_back(Ed(from,to,cap,0));
    edges.push_back(Ed(to,from,0,0));
    int t=edges.size();
    G[from].push_back(t-2);
    G[to].push_back(t-1);
    }

    bool bfs(int s,int t)
    {
    memset(d,-1,sizeof(d));
    queue<int> q;
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
    int now=q.front();q.pop();
    for(int i=0;i<(int)G[now].size();i++)
    {
    Ed &e=edges[G[now][i]];
    if(e.cap>e.flow&&d[e.to]==-1)
    {
    d[e.to]=d[now]+1;
    q.push(e.to);
    }
    }
    }
    return d[t]>=0;
    }

    int dfs(int now,int a)
    {
    if(now==n+1||a==0) return a;
    int flow=0,f;
    for(int &i=cur[now];i<(int)G[now].size();i++)
    {
    Ed &e=edges[G[now][i]];
    if(e.cap>e.flow&&d[e.to]==d[now]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
    {
    e.flow+=f;
    edges[G[now][i]^1].flow-=f;
    flow+=f;
    a-=f;
    if(a==0) break;
    }
    }
    return flow;
    }

    int Dinic()
    {
    int max_flow=0,s=1,t=n+1;
    while(bfs(s,t))
    {
    memset(cur,0,sizeof(cur));
    max_flow+=dfs(s,INF);
    }
    return max_flow;
    }

    int main()
    {
    /*freopen("input","r",stdin);*/
    scanf("%d%d",&n,&e);
    for(int i=1;i<=e;i++)
    {
    int a,b,w;
    scanf("%d%d%d",&a,&b,&w);
    add_edges(a,b,w);
    add_edges(b,a,w);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
    int k;
    scanf("%d",&k);
    add_edges(k,n+1,INF);
    }

    int ans=Dinic();
    printf("%d\n",ans);
    return 0;
    }

    /* Accepted, time = 30 ms, mem = 648 KiB, score = 100 2016年6月21日星期二 */
    ```

  • 0
    @ 2016-05-17 17:37:58

    试着直接实现了一遍《算法导论》上的GENERIC-PUSH-RELABEL算法,代码好长。。。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;

    const int inf = 0x7fffffff;
    const int maxn = 110;
    const int maxe = 310;
    int n, e, m;
    int s, t;
    int maxf;
    int next[maxn];
    int front[maxn];
    int h[maxn];
    int w[maxn];

    struct edge {
    int from;
    int to;
    int f;
    int c;
    edge (int from, int to, int f, int c) : from(from), to(to), f(f), c(c) {}
    };

    vector<edge> edges;
    vector<int> g[maxn];

    void add (int u, int v, int w) {
    int m = edges.size();
    edges.push_back (edge (u, v, 0, w));
    g[u].push_back (m);
    }

    void init (int s) {
    h[s] = t;
    for (int i = 0; i < g[s].size(); i++) {
    edge &p = edges[g[s][i]];
    w[p.to] = p.f = p.c;
    w[s] -= p.c;
    }
    }

    void push (int u, int cur) {
    edge &p = edges[g[u][cur]];
    edge &q = edges[g[u][cur] + 1];
    int temp = min (w[u], p.c - p.f);
    if (p.c) p.f += temp;
    else q.f -= temp;
    w[u] -= temp;
    w[p.to] += temp;
    }

    void relable (int u) {
    int res = inf;
    for (int i = 0; i < g[u].size(); i++) {
    res = min(res, h[edges[g[u][i]].to]);
    }
    h[u] = res + 1;
    }

    void discharge (int u) {
    int cur = 0;
    while (w[u] > 0) {
    if (cur == g[u].size()) {
    relable (u);
    cur = 0;
    }
    else if (edges[g[u][cur]].c > edges[g[u][cur]].f && h[u] == h[edges[g[u][cur]].to] + 1) push (u, cur);
    else cur++;
    }
    }

    void rtf (int s, int t) {
    for (int i = 2; i < t; i++) {
    next[i] = i + 1;
    front[i] = i - 1;
    }
    front[2] = 0;
    next[t - 1] = 0;
    int u = next[2];
    int head = 2;
    while (u) {
    int old_height = h[u];
    discharge (u);
    if (h[u] > old_height) {
    next[front[u]] = next[u];
    front[next[u]] = front[u];
    front[head] = u;
    front[u] = 0;
    next[u] = head;
    head = u;
    }
    u = next[u];
    }
    }

    int main ()
    {
    //freopen ("in.txt", "r", stdin);
    cin >> n >> e;
    int temu, temv, temw;
    for (int i = 0; i < e; i++) {
    cin >> temu >> temv >> temw;
    add (temu, temv, temw);
    add (temv, temu, 0);
    add (temv, temu, temw);
    add (temu, temv, 0);
    }
    s = 1;
    t = n + 1;
    cin >> m;
    for (int i = 0; i < m; i++) {
    cin >> temu;
    add (temu, t, inf);
    add (t, temu, 0);
    }
    init (s);
    rtf (s, t);
    for (int i = 0; i < g[s].size(); i++) {
    maxf += edges[g[s][i]].f;
    }
    cout << maxf;
    return 0;
    }
    ```

  • 0
    @ 2016-03-10 18:12:57

    令人振奋,第一道网络流就一遍AC了!
    虽然我存边的方式很丑,用了邻接矩阵,还存了每个点有多少出边。。。毕竟不想写前向星,看到数据范围就懒了
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #define INF 2147383647
    //dinic
    //BFS FIRST AND TAG
    //THEN DFS EVERYTIME UNTIL NOT FIND NEW PATH
    //THEN BFS AGAIN UNTIL NOT REACH THE END
    using namespace std;
    int n,m,e;
    int map[105][105];
    int edge[105][105];
    int tag[105];
    int q[200];
    int ans=0;
    bool book[105];
    bool bfs() {
    memset(tag,0,sizeof(tag));
    int head=1,tail=2;
    q[1]=1;
    tag[1]=1;
    while (head<tail) {
    if (q[head]==0)
    return 1;
    for (int i=1,u=q[head],v;i<=edge[q[head]][0];i++) {
    v=edge[q[head]][i];
    if (tag[v]==0 && map[u][v]>0) {
    q[tail++]=v;
    tag[v]=tag[u]+1;
    }
    }
    head++;
    }
    return 0;
    }
    int dfs(int x,int flow) {
    if (x==0) {
    return flow;
    }
    for (int i=1,y;i<=edge[x][0];i++) {
    y=edge[x][i];
    if (!book[y] && tag[y]>tag[x] && map[x][y]>0) {
    book[y]=1;
    int res=dfs(y,min(flow,map[x][y]));
    if (res>0) {
    map[x][y]-=res;
    map[y][x]+=res;
    return res;
    }
    }
    }
    return 0;
    }
    int main() {
    scanf("%d%d",&n,&e);
    for (int i=1,a,b,w;i<=e;i++) {
    scanf("%d%d%d",&a,&b,&w);
    edge[a][++edge[a][0]]=b;
    edge[b][++edge[b][0]]=a;
    map[a][b]=map[b][a]=w;
    }
    scanf("%d",&m);
    for (int i=1,tp;i<=m;i++) {
    scanf("%d",&tp);
    edge[tp][++edge[tp][0]]=0;
    map[tp][0]=INF;
    }
    while (bfs()) {
    while (1) {
    memset(book,0,sizeof(book));
    int res=dfs(1,INF);
    if (res==0) break;
    ans+=res;
    }
    }
    printf("%d",ans);
    return 0;

    }

  • 0
    @ 2016-02-02 14:49:28

    一百题纪念!!!(模板网络流)
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    #define N 20000+100
    #define INF 1<<29
    using namespace std;
    int nn;
    int h[N];
    int n,m,w;
    int s,t;
    int temp,ans;
    int p[N],q[N];
    struct node
    {
    int b,next,w;
    }e[N];
    void add(int x,int y,int z)
    {
    nn++;
    e[nn].b=y;
    e[nn].w=z;
    e[nn].next=p[x];
    p[x]=nn;
    }
    bool BFS()
    {
    for(int i=s;i<=t;i++)h[i]=0;
    int l=0,r=0;
    q[r++]=1;
    h[s]=1;
    while(l<r)
    {
    int k=q[l++];
    if(k==n)return true;
    for(int i=p[k];i;i=e[i].next)
    {
    int v=e[i].b;
    if(!h[v]&&e[i].w>0)
    {
    q[r++]=v;
    h[v]=h[k]+1;
    }
    }
    }
    return false;
    }
    int dinic(int pos,int max_flow)
    {
    if(pos==n)return max_flow;
    int ans=0;
    for(int i=p[pos];i;i=e[i].next)
    {
    int k=e[i].b,v=e[i].w;
    if(v>0&&h[k]==h[pos]+1)
    {
    int minv=min(v,max_flow-ans);
    v=dinic(k,minv);
    e[i].w-=v;
    e[i^1].w+=v;
    ans+=v;
    if(ans==max_flow)return ans;
    }

    }
    return ans;
    }
    int solve()
    {
    int sum=0;
    while(BFS())
    {
    sum+=dinic(s,INF);
    }
    return sum;
    }
    int main()
    {
    //freopen("D:\in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    add(a,b,c);
    add(b,a,c);
    }
    s=1;
    t=n;
    scanf("%d",&w);
    for(int i=1;i<=w;i++)
    {
    int tx;
    scanf("%d",&tx);
    add(tx,t,1<<29);
    }
    printf("%d",solve());
    return 0;
    }

  • 0
    @ 2016-02-01 16:42:43

    大神说最大流过了,算法就入门了 好激动。。。楼下说的很不错,提供一个dfs找增广路代码
    #include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;

    int n, e;
    int End;
    #define INF 100000000
    // end = n+1

    struct edge {
    int from, to, dis;
    int next;
    } edges[1000];
    int pos = 0;
    int head[1000];
    bool markedUnlink[1000];
    bool markedVisiting[1000];
    stack<int> edgeSub;

    void push(int from, int to, int dis)
    {
    edges[++pos].from = from;
    edges[pos].to = to;
    edges[pos].dis = dis;
    edges[pos].next = head[from];
    head[from] = pos;
    }
    ////////////////////////////////////

    int dfsFindPath(int from) {
    if (markedUnlink[from] || markedVisiting[from]) return 0;
    // not linked or is visiting
    if (from == End) return INF;
    markedVisiting[from] = true;
    for (int v = head[from]; v; v = edges[v].next) {
    int length = min(edges[v].dis, dfsFindPath(edges[v].to));
    if (length > 0) {
    edgeSub.push(v);
    markedVisiting[from] = false;
    return length;
    }
    }
    markedUnlink[from] = true;
    return 0;
    }

    int maxFlow()
    {
    int anslength = 0;
    while (1) {
    int addlength = dfsFindPath(1);
    while (!edgeSub.empty()) {
    edges[edgeSub.top()].dis -= addlength;
    edgeSub.pop();
    }
    if (addlength == 0)
    return anslength;
    anslength += addlength;
    }
    }

    int main()
    {
    memset (head,0,sizeof(head));
    memset (markedUnlink,0,sizeof(markedUnlink));
    memset (markedVisiting,0,sizeof(markedVisiting));
    int w;
    cin >> n >> e;
    End = n+1;
    for (int i = 1; i <= e; i ++) {
    int a, b, l;
    cin >> a >> b >> l;
    push(a,b,l);
    push(b,a,l);
    }
    cin >> w;
    for (int i = 1; i <= w; i++) {
    int t;
    cin >> t;
    push(t,n+1,INF);
    }
    cout << maxFlow() << endl;
    return 0;
    }

  • 0
    @ 2015-10-30 11:15:33

    裸最小割 根据最小割最大流定理 就是求最大流,建立一个超级汇点n+1 把所有的传送点加一条到n+1,容量为无限大的边,然后求1到n+1的最大流
    用的lrj书上的的dinic算法

    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <cstring>
    using namespace std;
    struct edge{
    int cap,flow,from,to;
    edge(){}
    edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
    };
    const int N=10010,INF=2099999999;
    vector<edge> edges;
    vector<int> g[N];
    int d[N],vis[N],cur[N],s,t,n,e,a,b,w,m,ans;

    void add(int from,int to,int cap){
    edges.push_back(edge(from,to,cap,0));
    edges.push_back(edge(to,from,cap,cap));
    int m=edges.size();
    g[from].push_back(m-2);
    g[to].push_back(m-1);
    }

    bool bfs(){
    queue<int> q;
    memset(vis,0,sizeof(vis));
    vis[s]=true;q.push(s);
    while(!q.empty()){
    int x=q.front();q.pop();
    for(int i=0;i<g[x].size();i++){
    if(!vis[edges[g[x][i]].to] && edges[g[x][i]].cap>edges[g[x][i]].flow )
    d[edges[g[x][i]].to]=d[x]+1,vis[edges[g[x][i]].to]=true,q.push(edges[g[x][i]].to);
    }
    }
    return vis[t];
    }
    int dfs(int x,int a){//a表示从开始到现在的最小残量
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int& i=cur[x];i<g[x].size();i++){
    edge& e=edges[g[x][i]];
    if( d[x]+1==d[e.to] && (f=dfs(e.to,min(a,e.cap-e.flow)))>0){
    e.flow+=f;edges[g[x][i]^1].flow-=f;//处理这条边和反向边
    flow+=f;a-=f;//处理之前的边
    if(a==0) break;
    }
    }
    return flow;
    }
    int maxflow(){
    int flow=0;
    while(bfs()){
    memset(cur,0,sizeof(cur));
    flow+=dfs(s,INF);
    }
    return flow;
    }

    int main(){
    freopen("1524.in","r",stdin);freopen("1524.out","w",stdout);
    scanf("%d%d",&n,&e);
    for(int i=1;i<=e;i++) scanf("%d%d%d",&a,&b,&w),add(a,b,w),add(b,a,w);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",&a),add(a,n+1,INF);
    s=1,t=n+1;
    ans=maxflow();
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2013-05-11 14:04:52

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 276 KiB, score = 10
    Accepted, time = 0 ms, mem = 276 KiB, score = 100

    终于0S了。。。。
    sap+gap....
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    #define MAXN 100

    int map[MAXN][MAXN];
    int h[MAXN];
    int n,m;
    int gap[MAXN];

    bool f;

    int sap(int v,int flow){
    int rec=0,minh=n;
    // printf("%d %d\n",v,flow);
    // for (int i=0;i++<n+1;) printf("%d ",h[i]);
    // printf("\n\n");
    if (v==n+1){
    f=true;
    return flow;
    }
    for (int i=0;i++<n+1;){
    if (map[v][i]){
    if (h[i]==h[v]-1){
    int ret=sap(i,min(flow-rec,map[v][i]));
    map[v][i]-=ret;
    map[i][v]+=ret;
    rec+=ret;
    if (flow==rec) return flow;
    if (h[1]>=n+1) return rec;
    }
    minh=min(h[i],minh);
    }
    }
    if (!f){
    h[v]=minh+1;
    }
    if (!(--gap[h[v]])){
    h[1]=n+1;
    }

    gap[h[v]]++;
    return rec;
    }

    int main(){
    int ans=0;
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n+1;i++){
    for (int j=0;j<=n+1;j++){
    map[i][j]=0;
    }
    }
    for (int i=0;i<=n+1;i++){
    h[i]=0;
    }
    while (m--){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    map[x][y]+=z;
    map[y][x]+=z;
    }
    scanf("%d",&m);
    while (m--){
    int x;
    scanf("%d",&x);
    map[x][n+1]=100000;
    }
    gap[0]=n+1;
    while (h[1]<n+1){
    f=false;
    ans+=sap(1,0x7ffffff);
    }
    printf("%d\n",ans);
    // system("pause");
    return 0;
    }

  • 0
    @ 2012-08-01 19:25:36

    注意是无向图啊、、、70分的自重啊、、、

  • 0
    @ 2010-07-17 09:25:07

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2010-04-13 18:34:18

    如楼下所言……赤裸裸的最小割……

    第一遍没法显示无向图……结果70分

    第二遍加了一句话AC

    无语中……

    至于最大流为什么等于最小割(最大流最小割定理),问问题的人可以想一下,如果把s和t看成两个集合……每条边就相当于一个门槛……而最小割就是那个最难逾越的门槛,所以流量一定是小于等于最小割的,即最大流等于最小割……

  • 0
    @ 2010-03-11 20:22:42

    裸的 - =

  • 0
    @ 2010-03-11 20:20:35

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    很明显的最小割

  • 0
    @ 2010-03-06 12:10:31

    Accepted 有效得分:100 有效耗时:0ms

    朴素网络流,设置超级汇点,求一遍原点1到超级汇点的最大流就好了

信息

ID
1524
难度
5
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
1300
已通过
463
通过率
36%
上传者