BZOJ 3265 志愿者招募增强版 单

标题效果：同1061 只是间隔为每种类型的志愿工作是多级

这是卡网络流量？未知

所有在所有的1061您将可以更改为在稍微改变- -

#include

#include

#include

#include

#include

#define INF 1e10

#define EPS 1e-7

using namespace std;

int m,n;

namespace Linear_Programming{

double A[10100][1010],b[10100],c[1010],v;

void Pivot(int l,int e)

{

int i,j;

b[l]/=A[l][e];

for(i=1;i<=n;i++)

if(i!=e)

A[l][i]/=A[l][e];

A[l][e]=1/A[l][e];

for(i=1;i<=m;i++)

if(i!=l&&fabs(A[i][e])>EPS)

{

b[i]-=A[i][e]*b[l];

for(j=1;j<=n;j++)

if(j!=e)

A[i][j]-=A[i][e]*A[l][j];

A[i][e]=-A[i][e]*A[l][e];

}

v+=c[e]*b[l];

for(i=1;i<=n;i++)

if(i!=e)

c[i]-=c[e]*A[l][i];

c[e]=-c[e]*A[l][e];

}

double Simplex()

{

int i,l,e;

while(1)

{

for(i=1;i<=n;i++)

if(c[i]>EPS)

break;

if((e=i)==n+1)

return v;

double temp=INF;

for(i=1;i<=m;i++)

if( A[i][e]>EPS && b[i]/A[i][e]

temp=b[i]/A[i][e],l=i;

if(temp==INF) return INF;

Pivot(l,e);

}

}

}

int main()

{

using namespace Linear_Programming;

int i,j,k,x,y;

cin>>n>>m;

for(i=1;i<=n;i++)

scanf("%lf",&c[i]);

for(i=1;i<=m;i++)

{

scanf("%d",&k);

for(j=1;j<=k;j++)

{

scanf("%d%d",&x,&y);

for(;x<=y;x++)

A[i][x]+=1.0;

}

scanf("%lf",&b[i]);

}

double ans=Simplex();

printf("%d\n",int(ans+0.5));

return 0;

}

好文阅读