【费用流】bzoj1520 [POI2006]Szk-Schools
2024-08-27 06:09:53
注意:建图的时候,一定要把旧标号相同的分开。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 5001
#define MAXM 100001
#define INF 2147483647
int S,T,n,x,A,B,C;
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(first,-,sizeof(first));en=;S=;T=(n<<|);}
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,,sizeof(inq));
d[S]=; inq[S]=; p[S]=; a[S]=INF; q.push(S);
while(!q.empty())
{
int U=q.front(); q.pop(); inq[U]=;
for(int i=first[U];i!=-;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]]=;}
}
}
if(d[T]>) return ;
Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;
while(U!=S)
{
cap[p[U]]-=a[T]; cap[p[U]^]+=a[T];
U=u[p[U]];
}
return ;
}
void Mincost()
{
int Flow=,Cost=;
while(Spfa(Flow,Cost));
if(Flow==n) printf("%d\n",Cost);
else puts("NIE");
}
int Abs(const int &v){return v< ? -v : v;}
int main()
{
scanf("%d",&n); Init_MCMF();
for(int j=;j<=n;++j)
{
scanf("%d%d%d%d",&x,&A,&B,&C);
AddEdge(S,j,,);
for(int i=A;i<=B;++i) AddEdge(j,i+n,,Abs(i-x)*C);
}
for(int i=;i<=n;++i) AddEdge(i+n,T,,);
Mincost();
return ;
}
最新文章
- 实现bootstrap布局的input输入框中的图标点击功能
- spring boot入门例子
- 6/19 sprint3 看板和燃尽图的更新
- apiCloud中图片裁剪模块FNImageClip的使用
- PlayerPrefs存储数据在本地的存储位置
- poj2286The Rotation Game(迭代加深dfs)
- CPU 球迷助威清理灰尘图形的全过程
- Android从raw、assets、SD卡中获取资源文件内容
- C语言面试问答5
- meta常用标签总结
- Linux系统用户管理
- Mybatis分页插件PageHelper简单使用
- 线性回归预测PM2.5----台大李宏毅机器学习作业1(HW1)
- 【翻译】WhatsApp 加密概述(技术白皮书)
- SPOJ-LCS Longest Common Substring 【后缀自动机】
- IrisSkin 单独控件样式设置 不使用皮肤样式
- 修改AD FS
- web api 安全
- 【bzoj 3524】[Poi2014]Couriers
- BZOJ3545 [ONTAK2010]Peaks kruskal 并查集 主席树 dfs序