POJ 网络流

poj3436 ACM Computer Factory

题意：每台电脑有p个零件，有n台加工电脑的机器，每台机器可以处理某一种未加工完成的电脑，给出该机器加工前电脑必须所拥有的零件和加工后该电脑所拥有的零件，以及每小时可以加工的数量c[i]，问你这些机器每小时最多可以同时加工成多少台完整的电脑。

对于每台机器i(1<=i<=n)，拆成两个点i，i+n，连一条边i->i+n,其容量为c[i],设一个超级源点0和超级汇点$2n+1$,对于初始零件为0的电脑i，连一条边0->i,对于加工后零件为n的定案哦，连一条边$i+n->2n+1$,求出最大流并记录每条边流量即可

#include
#include
#include
#include
using namespace std;
const int MAXN=1000,MAXM=100000,inf=1e9;
int in[505][12],out[505][12],V[55];
int s[505][505];
bool mp[55][55];
int p,n;
    struct Edge
    {
        int v,c,f,nx;
        Edge() {}
        Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
    } E[MAXM];
    int G[MAXN],cur[MAXN],dis[MAXN],gap[MAXN],N,sz;
    void init(int _n)
    {
        N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
    }
    void link(int u,int v,int c)
    {
        E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
        E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
    }
    bool bfs(int S,int T)
    {
        static int Q[MAXN]; memset(dis,-1,sizeof(dis[0])*N);
        dis[S]=0; Q[0]=S;
        for (int h=0,t=1,u,v,it;hE[it].f)
                {
                    dis[v]=dis[u]+1; Q[t++]=v;
                }
            }
        }
        return dis[T]!=-1;
    }
    int dfs(int u,int T,int low)
    {
        if (u==T) return low;
        int ret=0,tmp,v;
        for (int &it=cur[u];~it&&retE[it].f)
            {
                if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
                {
                    ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp;
                    //if(u!=0&&v!=2*n+1&&v!=u+n)
                    s[u-n][v]+=tmp;
                }
            }
        }
        if (!ret) dis[u]=-1; return ret;
    }
    int dinic(int S,int T)
    {
        int maxflow=0,tmp;
        while (bfs(S,T))
        {
            memcpy(cur,G,sizeof(G[0])*N);
            while (tmp=dfs(S,T,inf)) maxflow+=tmp;
        }
        return maxflow;
    }

bool pan(int x,int y){
    for(int i=1;i<=p;i++){
        if(in[y][i]==2)
            continue;
        if(in[y][i]!=out[x][i])
            return false;
    }
    return true;
}
int main(){

    scanf("%d%d",&p,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&V[i]);
        for(int j=1;j<=p;j++)
            scanf("%d",&in[i][j]);
        for(int j=1;j<=p;j++)
            scanf("%d",&out[i][j]);
    }
    init(n*2+2);
  //  cout<<-2<p)
            link(0,i,V[i]);
    }
    for(int i=n+1;i<=n*2;i++){
        int j;
        for(j=1;j<=p;j++){
            if(out[i-n][j]!=1)
                break;
        }
        if(j>p)
            link(i,n*2+1,V[i-n]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j){
                if(mp[i][j]==1)
                    link(i+n,j,V[i]);
            }

     printf("%d",dinic(0,n*2+1));
     int ans=0;
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++){
            if(s[i][j]>0)
                ans++;
         }
     printf(" %d\n",ans);
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++){
             if(s[i][j]>0)
                 printf("%d %d %d\n",i,j,s[i][j]);
        }
}

poj1087 A Plug for UNIX

这题意真的有毒。。。

题意：已知有n个插座，m个需要充电的电器，每个电器有一种对应的插座，有k种适配器，每种适配器有无限个，适配器可以将插座j改为插座i（j先输入），问你最少有多少个·电器没有对应的插座可以插

设一个超级源点s和超级汇点t，对于每个插座，从s连一条边到该插座，容量为1，从所有电器连一条边到汇点，容量为1，从所有适配器的接入插座到输出插座连一条容量为无穷的边，求一下最大流即可，输出n-最大流

#include
#include