【分析】
表示初看觉得这题很经典但是仔细想想发现我不会ORZ。。
表示不会单纯形法搞线性规划【要学么？
之前做的网络流24题都没有涉及到线性规划的转化的。。
这道的确是经典题，但是转化挺难的。。
推荐博客！！https://www.byvoid.com/zhs/blog/noi-2008-employee#more-916
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxm 10010
#define INF 0xfffffff int mymin(int x,int y) {return x<y?x:y;} int n,m; struct node
{
int x,y,f,c,o,next;
}t[*Maxm];
int first[Maxn],len; void ins(int x,int y,int f,int c)
{
t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;t[len].o=len+;
t[len].next=first[x];first[x]=len;
t[++len].x=y;t[len].y=x;t[len].f=;t[len].c=-c;t[len].o=len-;
t[len].next=first[y];first[y]=len;
} int nd[Maxn];
int dis[Maxn],flow[Maxn],pre[Maxn],st,ed;
bool inq[Maxn];
queue<int > q; void bfs()
{
while(!q.empty()) q.pop();
// memset(dis,-1,sizeof(dis));
for(int i=;i<=ed;i++) dis[i]=INF;
memset(inq,,sizeof(inq));
dis[st]=;inq[st]=;q.push(st);
flow[st]=INF;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
pre[y]=i;
flow[y]=mymin(flow[x],t[i].f);
if(!inq[y])
{
q.push(y);
inq[y]=;
}
}
}
q.pop();inq[x]=;
}
} void max_flow()
{
int sum=;
while()
{
bfs();
if(dis[ed]==INF) break;
sum+=dis[ed]*flow[ed];
int x=ed;
while(x!=st)
{
t[pre[x]].f-=flow[ed];
t[t[pre[x]].o].f+=flow[ed];
x=t[pre[x]].x;
}
}
printf("%d\n",sum);
} void output()
{
for(int i=;i<=len;i+=)
{
printf("%d -> %d = %d , %d \n",t[i].x,t[i].y,t[i].f,t[i].c);
}
} int main()
{
scanf("%d%d",&n,&m);
len=;
for(int i=;i<=n;i++) scanf("%d",&nd[i]);
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
ins(l,r+,INF,c);
}
for(int i=;i<=n;i++) ins(i+,i,INF,);
nd[]=;
st=n+;ed=st+;
for(int i=;i<=n;i++) if(nd[i]-nd[i-]>) ins(st,i,nd[i]-nd[i-],);
else if(nd[i]-nd[i-]<) ins(i,ed,nd[i-]-nd[i],);
ins(n+,ed,nd[n],);
// output();
max_flow();
return ;
}
建图超机智的，我想不到啊！！
2017-02-25 10:55:41
【今天我要用单纯形水这题】
【趁我还记得模板怎么背】
【---需要初始化版本】
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
#define Maxm 1010
#define Maxn 10010
const double eps=1e-,INF=1e15; int m,n; double a[Maxm][Maxn];
// int id[Maxn*2]; double myabs(double x) {return x>?x:-x;} void Pivot(int l,int e)
{
// swap(id[l+n],id[e]);
double t=a[l][e];a[l][e]=;
for(int j=;j<=n;j++) a[l][j]/=t;
for(int i=;i<=m;i++) if(i!=l&&myabs(a[i][e])>eps)
{
t=a[i][e];a[i][e]=;
for(int j=;j<=n;j++) a[i][j]-=a[l][j]*t;
}
} bool init()
{
while()
{
int l=,e=;
for(int i=;i<=m;i++) if(a[i][]<-eps&&(!l||(rand()&))) l=i;
if(!l) break;
for(int j=;j<=n;j++) if(a[l][j]<-eps&&(!e||(rand()&))) e=j;
if(!e) return ;
Pivot(l,e);
}
return ;
} bool simplex()
{
while()
{
int l=,e=;double mn=INF;
for(int j=;j<=n;j++) if(a[][j]>eps) {e=j;break;}
if(!e) break;
for(int i=;i<=m;i++) if(a[i][e]>eps&&mn>a[i][]/a[i][e])
mn=a[i][]/a[i][e],l=i;
if(!l) return ;
Pivot(l,e);
}
return ;
} int main()
{
srand();
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++) {scanf("%lf",&a[i][]);a[i][]=-a[i][];}
for(int i=;i<=n;i++)
{
int s,t;
scanf("%d%d%lf",&s,&t,&a[][i]);a[][i]=-a[][i];
for(int j=s;j<=t;j++) a[j][i]=-;
}
if(init()&&simplex())
{
printf("%.0lf\n",a[][]);
}
else printf("-1\n");
return ;
}
【对偶版本，不需要初始化，快10s！！！】
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
#define Maxm 1010
#define Maxn 10010
const double eps=1e-,INF=1e15; int m,n; double a[Maxn][Maxm];
// double a[Maxm][Maxn];
// int id[Maxn*2]; double myabs(double x) {return x>?x:-x;} void Pivot(int l,int e)
{
// swap(id[l+n],id[e]);
double t=a[l][e];a[l][e]=;
for(int j=;j<=n;j++) a[l][j]/=t;
for(int i=;i<=m;i++) if(i!=l&&myabs(a[i][e])>eps)
{
t=a[i][e];a[i][e]=;
for(int j=;j<=n;j++) a[i][j]-=a[l][j]*t;
}
} bool init()
{
while()
{
int l=,e=;
for(int i=;i<=m;i++) if(a[i][]<-eps&&(!l||(rand()&))) l=i;
if(!l) break;
for(int j=;j<=n;j++) if(a[l][j]<-eps&&(!e||(rand()&))) e=j;
if(!e) return ;
Pivot(l,e);
}
return ;
} bool simplex()
{
while()
{
int l=,e=;double mn=INF;
for(int j=;j<=n;j++) if(a[][j]>eps) {e=j;break;}
if(!e) break;
for(int i=;i<=m;i++) if(a[i][e]>eps&&mn>a[i][]/a[i][e])
mn=a[i][]/a[i][e],l=i;
if(!l) return ;
Pivot(l,e);
}
return ;
} int main()
{
srand();
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++) {scanf("%lf",&a[][i]);a[][i]=a[][i];}
for(int i=;i<=n;i++)
{
int s,t;
scanf("%d%d%lf",&s,&t,&a[i][]);a[i][]=a[i][];
for(int j=s;j<=t;j++) a[i][j]=;
}
swap(n,m);
if(/*init()&&*/simplex())
{
printf("%.0lf\n",-a[][]);
}
else printf("-1\n");
return ;
}
对偶就是i和j反，系数正负全反。。。