POJ-3436 拆點做最大流

      這道題好長..看了好久才看懂..囧..也就是說每個machine對于電腦半成品所包含零件的輸入有三種要求..0代表不能有該零件輸入..1代表必須有該零件輸入..2代表有或沒有無所謂...而每個machine産生的電腦半成品中每個零件有兩種狀态..0代表半成品包含該零件,1代表半成品不包含該零件..題目中最開始是給一堆沒有任何零件的半成品..最終需要的是所有零件都包含的成品..問最多能得到多少成品電腦..

      建立一個超級源點，其所有的s[]為0,Q為無窮大..建立一個超級彙點，其所有的d[]為1,Q為無窮大...将所有的點拆成彙點和出點，彙點到出點的流量為其Q..一個machine的結果滿足另一個machine的輸入的建立有向線段...在這個過程中超級源點和超級彙點都參與..

     從超級源點到超級彙點跑最大流..最大流的結果就是輸出的最多成品電腦數..

     而要得出用了哪些路徑，每條路徑流過的流量.那麼就判斷輸入時的那些個個machine間的有向線段剩餘容量的變化..

Program:

#include<iostream>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<queue>
#define oo 2000000000
using namespace std;
struct node1
{
      int Q,s[11],d[11];
}machine[55];
struct node2
{
      int x,y,c,next;
}line[20005];
int n,p,m,_link[205],ans,num,way[505],dis[205];
bool inqueue[205];
queue<int> myqueue;
bool BFS()
{
      int h,k;
      while (!myqueue.empty()) myqueue.pop();
      memset(dis,0,sizeof(dis));
      dis[0]=1;
      myqueue.push(0);
      while (!myqueue.empty())
      {
            h=myqueue.front();
            myqueue.pop();
            k=_link[h];
            while (k)
            {
                  if (line[k].c && !dis[line[k].y])
                  {
                         dis[line[k].y]=dis[h]+1;
                         myqueue.push(line[k].y);
                  }
                  k=line[k].next;
            }
      }
      return dis[n];
}
bool DFS(int p,int Flow)
{
      int k;
      if (p==n)
      {
            ans+=Flow;
            for (k=1;k<=num;k++)
            {
                   line[way[k]].c-=Flow; 
                   m++;
                   line[m].c=Flow;
                   line[m].x=line[way[k]].y;
                   line[m].y=line[way[k]].x;
                   line[m].next=_link[line[m].x];
                   _link[line[m].x]=m;
            }
            return true;
      }
      num++;
      k=_link[p];
      while (k)
      {
            if (line[k].c && dis[line[k].y]-dis[p]==1)
            {
                  way[num]=k;
                  if (DFS(line[k].y,min(Flow,line[k].c))) return true;
            }
            k=line[k].next;
      }
      num--;
      return false;
}
void MaxFlow()
{
      ans=0;
      while (BFS())
      {
            num=0;
            DFS(0,oo);
      }
      return;
}
int main()
{
      int i,j,k,h;
      scanf("%d%d",&p,&n);
      memset(machine,0,sizeof(machine));
      memset(_link,0,sizeof(_link));
      for (i=1;i<=n;i++)
      {
             scanf("%d",&machine[i].Q);
             for (j=1;j<=p;j++) scanf("%d",&machine[i].s[j]);
             for (j=1;j<=p;j++) scanf("%d",&machine[i].d[j]);
      }
      n++;
      machine[0].Q=machine[n].Q=oo; 
      for (j=1;j<=p;j++) machine[n].s[j]=1;
      m=0;
      for (i=1;i<=n;i++)
      {
            m++;
            line[m].x=i*2-1; line[m].y=i*2; line[m].c=machine[i].Q;
            line[m].next=_link[line[m].x];
            _link[line[m].x]=m;
      } 
      for (i=0;i<n;i++)
         for (j=1;j<=n;j++)
         if (i!=j)
         {
               if (!i && j==n) continue;
               for (k=1;k<=p;k++)
                 if (machine[j].s[k]==1 && !machine[i].d[k] ||
                       !machine[j].s[k] &&  machine[i].d[k]) goto A;
               m++;
               line[m].x=i*2; line[m].y=j*2-1; line[m].c=oo;
               line[m].next=_link[line[m].x];   
               _link[line[m].x]=m;
               A: ;
         }
      n*=2;
      h=m;
      MaxFlow();
      num=0;
      for (i=n/2+1;i<=h;i++)
        if (line[i].c!=oo && line[i].x!=0 && line[i].y!=n-1)
            way[++num]=i; 
      printf("%d %d\n",ans,num);
      for (i=1;i<=num;i++) 
        printf("%d %d %d\n",line[way[i]].x/2,line[way[i]].y/2+1,oo-line[way[i]].c);
      return 0;
}