首页 > 代码库 > 【费用流】bzoj1520 [POI2006]Szk-Schools
【费用流】bzoj1520 [POI2006]Szk-Schools
注意:建图的时候,一定要把旧标号相同的分开。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 #define MAXN 5001 7 #define MAXM 100001 8 #define INF 2147483647 9 int S,T,n,x,A,B,C;10 int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array11 bool inq[MAXN];12 int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;13 queue<int>q;14 void Init_MCMF(){memset(first,-1,sizeof(first));en=0;S=0;T=(n<<1|1);}15 void AddEdge(const int &U,const int &V,const int &W,const int &C)16 {17 u[en]=U; v[en]=V; cap[en]=W; cost[en]=C;18 next[en]=first[U]; first[U]=en++;19 u[en]=V; v[en]=U; cost[en]=-C;20 next[en]=first[V]; first[V]=en++;21 }22 bool Spfa(int &Flow,int &Cost)23 {24 memset(d,0x7f,sizeof(d));25 memset(inq,0,sizeof(inq));26 d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);27 while(!q.empty())28 {29 int U=q.front(); q.pop(); inq[U]=0;30 for(int i=first[U];i!=-1;i=next[i])31 if(cap[i] && d[v[i]]>d[U]+cost[i])32 {33 d[v[i]]=d[U]+cost[i];34 p[v[i]]=i;35 a[v[i]]=min(a[U],cap[i]);36 if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}37 }38 }39 if(d[T]>2000000000) return 0;40 Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;41 while(U!=S)42 {43 cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];44 U=u[p[U]];45 }46 return 1;47 }48 void Mincost()49 {50 int Flow=0,Cost=0;51 while(Spfa(Flow,Cost));52 if(Flow==n) printf("%d\n",Cost);53 else puts("NIE");54 }55 int Abs(const int &v){return v<0 ? -v : v;}56 int main()57 {58 scanf("%d",&n); Init_MCMF();59 for(int j=1;j<=n;++j)60 {61 scanf("%d%d%d%d",&x,&A,&B,&C);62 AddEdge(S,j,1,0);63 for(int i=A;i<=B;++i) AddEdge(j,i+n,1,Abs(i-x)*C);64 }65 for(int i=1;i<=n;++i) AddEdge(i+n,T,1,0);66 Mincost();67 return 0;68 }
【费用流】bzoj1520 [POI2006]Szk-Schools
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。