POJ 3469-Dual Core CPU（Dinic 最大流/最小割算法）

Myth丶恋晨 2022-09-25 06:26 196阅读 0赞

Dual Core CPU

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;15000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;22932</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9983</td> 
  </tr> 
  <tr> 
   <td colspan="3" align="center" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;5000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.

The routine consists of *N* modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let's define them as *Ai* and *Bi*. Meanwhile, *M* pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.

Input

There are two integers in the first line of input data, *N* and *M* (1 ≤ *N* ≤ 20000, 1 ≤ *M* ≤ 200000) .  
The next *N* lines, each contains two integer, *Ai* and *Bi*.  
In the following *M* lines, each contains three integers: *a*, *b*, *w*. The meaning is that if module *a* and module *b* don't execute on the same core, you should pay extra *w* dollars for the data-exchange between them.

Output

Output only one integer, the minimum total cost.

Sample Input

3 1
    1 10
    2 10
    10 3
    2 3 1000

Sample Output

Source

[POJ Monthly--2007.11.25][], Zhou Dong

## 题目意思： ##

有两个CPU，它们之间有N个模块，每个模块必须运行在某个CPU中。

每个模块在每个CPU中运行的耗费分别是Ai和Bi。

有M对模块之间需要共享数据，如果它们不是在同一个CPU中运行，需要W的耗费，反之不需要。

如何安排这N个模块能够使得耗费最小？

## 解题思路： ##

因为每个模块必须运行在某个CPU中，所以想到要建图求最小割，又由最大流最小割定理可知，直接求出最大流即可。

注意要双边建图。

![20160815194004609][]

两块CPU分别作为源点和汇点，Ai是连接源点的容量，Bi是连接汇点的容量。

W连接两块需要共享数据的模块，建图如上，求解S到T的最大流即为最小割。

试了一下[Ford-Fulkerson 标号法求网络最大流][Ford-Fulkerson]……Orz可惜邻接矩阵不能开得太大，一直MLE…果断改Dinic！！

## ① ##

下面第一个AC对应的代码~

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <iomanip>
    #include <algorithm>
    #define max 21000
    #define maxn 1000000
    #define INF 0xfffffff
    using namespace std;
    struct edge
    {
        int to,cap,rev;//终点、容量、反向边
    };
    vector<edge>G[maxn];//图的邻接表表示
    int level[maxn];//顶点到源点的距离标号
    int iter[maxn];//当前弧，在其之前的边都已经没有用了
    void add_edge(int from,int to,int cap)//向图中增加一条从from到to的容量为cap的边
    {
        G[from].push_back((edge)
        {
            to,cap,G[to].size()
        });
        G[to].push_back((edge)
        {
            from,0,G[from].size()-1
        });
    }
    void bfs(int s)//通过BFS计算从源点出发的距离标号
    {
        memset(level,-1,sizeof(level));
        queue<int>que;
        level[s]=0;
        que.push(s);
        while(!que.empty())
        {
            int v=que.front();
            que.pop();
            for(int i=0; i<G[v].size(); ++i)
            {
                edge &e=G[v][i];
                if(e.cap>0&&level[e.to]<0)
                {
                    level[e.to]=level[v]+1;
                    que.push(e.to);
                }
            }
        }
    }
    int dfs(int v,int t,int f)//DFS寻找增广路
    {
        if(v==t) return f;
        for(int &i=iter[v]; i<G[v].size(); ++i)
        {
            edge &e=G[v][i];
            if(e.cap>0&&level[v]<level[e.to])
            {
                int d=dfs(e.to,t,min(f,e.cap));
                if(d>0)
                {
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
    int Dinic(int s,int t)//求解s到t的最大流
    {
        int maxflow=0;
        while(1)
        {
            bfs(s);
            if(level[t]<0) return maxflow;
            memset(iter,0,sizeof(iter));
            int f;
            while((f=dfs(s,t,INF))>0)
                maxflow+=f;
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int i,a,b,w;
        int n,m;
        cin>>n>>m;
        for(i=1; i<=n; ++i)
        {
            cin>>a>>b;
            add_edge(0,i,a);
            add_edge(i,n+1,b);
            add_edge(i,0,a);//双向边
            add_edge(n+1,i,b);
        }
        while(m--)
        {
            cin>>a>>b>>w;
            add_edge(a,b,w);
            add_edge(b,a,w);//双向边
        }
        cout<<Dinic(0,n+1)<<endl;
        return 0;
    }
    /*
    3 1
    1 10
    2 10
    10 3
    2 3 1000
    */

![20160815192241555][]

## ② ##

就是第二行AC对应的代码~

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <iomanip>
    #include <algorithm>
    #define nmax 21000
    #define mmax 1000000
    #define INF 0xfffffff
    using namespace std;
    struct Edge
    {
        int u,v,cap,flow;
        int next;
        Edge(int a=0,int b=0,int c=0,int d=0):u(a),v(b),cap(c),flow(d) {}
    };
    struct Edgelist
    {
        int start[nmax];
        int last[nmax];
        int t,i;
        Edge arc[mmax];
        void Clear()//清除
        {
            t=0;
            memset(last,-1,sizeof(last));
        }
        void Push_back(Edge edge)//追加
        {
            edge.next=-1;
            arc[t]=edge;
            if(last[edge.u]!=-1) arc[last[edge.u]].next=t;
            else start[edge.u]=t;
            last[edge.u]=t;
            ++t;
        }
        void add_arc(Edge edge//创建双向弧
        {
            Push_back(edge);
            Push_back(Edge(edge.v,edge.u,edge.cap));
        }
    } net;
    int q[2][nmax];//数组模拟滚动数列
    int q1[2],q2[2],qnow;
    void Push_queue(int a)//入队列
    {
        q[qnow][q2[qnow]++]=a;
    }
    int Pop_queue()//出队列
    {
        return q[qnow^1][q1[qnow^1]++];
    }
    void Switch_queue()//滚动队列
    {
        qnow^=1;
        q1[qnow]=0,q2[qnow]=0;
    }
    bool Empty_queue()//判空
    {
        return q1[qnow^1]>=q2[qnow^1];
    }
    int Size_queue()//大小
    {
        return q2[qnow^1]-q1[qnow^1];
    }
    int n,m;
    int dis[nmax];//层次网络（距离标号）
    int path[nmax],deep;//路径
    int cur[nmax];
    bool BFS()//构建层次网络
    {
        int i,l,u,v;
        memset(dis,-1,sizeof(dis));
        dis[0]=0;
        qnow=0;
        Switch_queue();
        Push_queue(0);
        Switch_queue();
        while(!Empty_queue())
        {
            l=Size_queue();
            while(l--)
            {
                u=Pop_queue();
                for(i=net.start[u]; i!=-1; i=net.arc[i].next)
                {
                    v=net.arc[i].v;
                    if(dis[v]==-1&&net.arc[i].cap>net.arc[i].flow)
                    {
                        Push_queue(v);
                        dis[v]=dis[u]+1;
                        if(v==n) return true;
                    }
                }
            }
            Switch_queue();
        }
        return false;
    }
    int Dinic()//求最大流
    {
        int i,u,neck,pos,res;
        int maxflow=0;
        while(BFS())
        {
            memcpy(cur,net.start,sizeof(cur));
            deep=u=0;
            while(1)//最短路增广
            {
                if(u==n)//存在增广路则修改残余网络
                {
                    neck=INF;
                    for(i=0; i<deep; ++i)
                    {
                        res=net.arc[path[i]].cap-net.arc[path[i]].flow;
                        if(res<neck)
                        {
                            neck=res;
                            pos=i;
                        }
                    }
                    maxflow+=neck;
                    for(i=0; i<deep; ++i)
                    {
                        net.arc[path[i]].flow+=neck;
                        net.arc[path[i]^1].flow-=neck;
                    }
                    deep=pos;
                    u=net.arc[path[deep]].u;
                }
                for(i=cur[u]; i!=-1; i=net.arc[i].next)//在层次网络中进行增广
                {
                    if(net.arc[i].cap>net.arc[i].flow&&dis[u]+1==dis[net.arc[i].v])
                        break;
                }
                cur[u]=i;
                if(i!=-1)
                {
                    path[deep++]=i;
                    u=net.arc[i].v;
                }
                else
                {
                    if(deep==0) break;
                    dis[u]=-1;
                    u=net.arc[path[--deep]].u;
                }
            }
        }
        return maxflow;//最大流
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int i,a,b,w;
        cin>>n>>m;
        net.Clear();
        for(i=1; i<=n; ++i)//插入弧
        {
            cin>>a>>b;
            net.add_arc(Edge(0,i,a));
            net.add_arc(Edge(i,n+1,b));
        }
        while(m--)
        {
            cin>>a>>b>>w;
            net.add_arc(Edge(a,b,w));
        }
        ++n;
        cout<<Dinic()<<endl;
        return 0;
    }
    /*
    3 1
    1 10
    2 10
    10 3
    2 3 1000
    */

[POJ Monthly--2007.11.25]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.11.25
[20160815194004609]: /images/20220718/19c649f21a3447a388a9d4d7d7a8530c.png
[Ford-Fulkerson]: http://blog.csdn.net/mikasa3/article/details/52201763
[20160815192241555]: /images/20220718/63afd8b9aa944b519430e1b9b1584bbf.png