【费用流】bzoj3280 小R的烦恼

类似bzoj1221 http://www.cnblogs.com/autsky-jadek/p/4174087.html

只不过大学有多个，所以我们另开一个节点汇总所有'S->大学'的边，然后再把这个节点和Yi相连即可。

死于初始化。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

#define MAXN 161

#define MAXM 40001

#define INF 2147483647

int S,T,Hos;

int N,M,K,sum;

int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array

bool inq[MAXN];

int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;

queue<int>q;

void Init_MCMF()

{

    memset(p,0,sizeof(p));

    memset(a,0,sizeof(a));

    memset(first,-1,sizeof(first));

    memset(next,0,sizeof(next));

    memset(u,0,sizeof(u));

    memset(v,0,sizeof(v));

    memset(cap,0,sizeof(cap));

    memset(cost,0,sizeof(cost));

    en=0;S=0;T=(N<<1)+M+2;Hos=T-1;sum=0;

}

void AddEdge(const int &U,const int &V,const int &W,const int &C)

{u[en]=U; v[en]=V; cap[en]=W; cost[en]=C; next[en]=first[U]; first[U]=en++;

u[en]=V; v[en]=U; cost[en]=-C; next[en]=first[V]; first[V]=en++;}

bool Spfa(int &Flow,int &Cost)

{

    memset(d,0x7f,sizeof(d));

    memset(inq,0,sizeof(inq));

    d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);

    while(!q.empty())

      {

        int U=q.front(); q.pop(); inq[U]=0;

        for(int i=first[U];i!=-1;i=next[i])

          if(cap[i] && d[v[i]]>d[U]+cost[i])

            {

              d[v[i]]=d[U]+cost[i];

              p[v[i]]=i;

              a[v[i]]=min(a[U],cap[i]);

              if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}

            }

      }

    if(d[T]>2100000000) return 0;

    Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;

    while(U!=S)

      {

        cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];

        U=u[p[U]];

      }

    return 1;

}

int Mincost()

{

    int Flow=0,Cost=0;

    while(Spfa(Flow,Cost));

    if(Flow<sum) puts("impossible");

    else printf("%d\n",Cost);

}

int A[51],B,C,D[51],E[51],zu;

int main()

{

	scanf("%d",&zu);

	for(int Z=1;Z<=zu;++Z)

	  {

	  	printf("Case %d: ",Z);

	  	scanf("%d%d%d",&N,&M,&K);

	    Init_MCMF();

	    for(int i=1;i<=N;++i) scanf("%d",&A[i]),sum+=A[i];

    	for(int i=1;i<=M;++i)

		  {

		  	scanf("%d%d",&B,&C);

		    AddEdge(S,i+(N<<1),B,C);

			AddEdge(i+(N<<1),Hos,INF,0);

		  }

    	for(int i=1;i<=K;++i) scanf("%d%d",&D[i],&E[i]);

    	for(int i=1;i<=N;++i)

    	  {

    	  	AddEdge(S,i,A[i],0);

            AddEdge(i+N,T,A[i],0);

            AddEdge(Hos,i+N,INF,0);

            if(i+1<=N) AddEdge(i,i+1,INF,0);

            for(int j=1;j<=K;++j)

              if(i+D[j]+1<=N)

                AddEdge(i,i+D[j]+1+N,INF,E[j]);

    	  }

    	Mincost();

	  }

	return 0;

}