POJ3469 - 构造图..做最大流..

这道题初看和网络流完全没关系.....以前做的一些网络流都是些模板题....这道题就要自己来构图了...

首先假设没有后面的两两不共存需要代价的条件....也就是只要一个程序去A处理器要多少代价...去B处理器要多少代价...问总共的最小代价..

构造图...源点为A处理器...中间一列需要执行的程序...汇点为B处理器..源点向所有的中间点做边...容量为每个程序放在A处理器执行的代价...所有中间点向汇点做边..容量为每个程序放在B处理器执行的代价....做一次最大流...可以发现得到的最大流即为所需的最小代价....

现在加入条件...给出哪几对不在一个处理器处理就要更多的代价...则将这两个点做两条边..x-->y容量为c...y-->x容量为c...因为每条增广路所流的流量是这条增广路上剩余容量最少的边的流量...通过做最大流依然能为我们筛选出最小的代价..

还有一点就是网络流的存储方式....网络流一般是用邻接矩阵最方便...但是这道题的数据量过大...用另接矩阵会爆空间...所以要采用一种即节省空间又不太耗时的方法...用一个数组存下所有边...然后用一种伪链表的方式来存储...详细见程序的insert段...这样就能做到省空间...最多要用多少边...就开多大数组...查询时特别是这里更新剩余网络时..相当方便和快捷..对两条流量向反的边处理很巧妙...每次建图的时候就将反向变建在当前边的下一位了...这就方便剩余网络的修改...细心点可以发现..这样每次都做一个反向边...那就很有可能会有若干条重复的边出现( 比如先做了 1->2 c=3...马上将下一位做 2->1 c=0....后面又读入一个 2 -> 1 c=2...马上将下一位做 1->2 c=0 ) 这样没有关系....不会有影响....因为我可以这条边做完了...再做下一个这条边..结果是一样的..

Program:

/*
   POJ3469 - 网络流巧妙构图
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 2000000000
#define SIZE 20010
using namespace std;
struct p1
{
   int x,y,c,next;
}line[2000001];
int N,M,x,y,c,t,v[SIZE],dis[SIZE],Num,UseLine[SIZE];
queue<int> Myqueue;
bool FindAWay;
void insert(int x,int y,int c)
{
    t++;
    line[t].x=x; line[t].y=y; line[t].c=c;
    line[t].next=v[x]; v[x]=t;
    t++;
    line[t].x=y; line[t].y=x; line[t].c=0;
    line[t].next=v[y]; v[y]=t;
}
bool BFS()
{
    int k,h;
    while (!Myqueue.empty()) Myqueue.pop();    
    memset(dis,0,sizeof(dis));
    Myqueue.push(1); dis[1]=1;
    while (!Myqueue.empty())
    {
         h=Myqueue.front(); Myqueue.pop();
         k=v[h];
         while (k!=-1)
         {
            if (!dis[line[k].y] && line[k].c)
            {
               dis[line[k].y]=dis[h]+1;
               if (line[k].y==N) return true;
               Myqueue.push(line[k].y);
            }
            k=line[k].next;
         }
    }
    return false;
}
int DFS(int h)
{
    int ans=0,k=v[h];
    if (h==N)
    { 
       int MinFlow=MAX;      
       for (int i=1;i<=Num;i++) MinFlow=MinFlow<line[UseLine[i]].c?MinFlow:line[UseLine[i]].c;
       for (int i=1;i<=Num;i++)
       { 
          line[UseLine[i]].c-=MinFlow;
          if (line[UseLine[i]+1].y==line[UseLine[i]].x)
            line[UseLine[i]+1].c+=MinFlow; else
              line[UseLine[i]-1].c+=MinFlow;
       }
       return MinFlow;
    }
    while (k!=-1)
    {
       if (line[k].c && dis[line[k].y]-dis[h]==1)
       {
           Num++;
           UseLine[Num]=k;
           ans+=DFS(line[k].y);
           if (FindAWay)
           {
               if (line[k].c) return ans;
               FindAWay=false;
           }
           Num--;
       }
       k=line[k].next;
    }
    return ans;
}
int Dinic()
{
    int ans=0,flow;
    while (BFS())
    {
        FindAWay=false; Num=0;
        if (flow=DFS(1)) ans+=flow;
    }
    return ans;
}
int main()
{
    freopen("3469.in","r",stdin);
    freopen("3469.out","w",stdout);
    scanf("%d%d",&N,&M);  t=0;
    memset(v,-1,sizeof(v));
    for (int i=1;i<=N;i++)
    {
       scanf("%d%d",&x,&y);
       insert(1,i+1,x); insert(i+1,N+2,y);
    }
    while (M--)
    {
       scanf("%d%d%d",&x,&y,&c);
       insert(x+1,y+1,c); insert(y+1,x+1,c);
    }
    N+=2; 
    printf("%d\n",Dinic());
    return 0;
}