BZOJ 3265 志願者招募加強版 單純形

BZOJ 3265 志願者招募加強版 單純形

這是卡網絡流？不明

總之把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]>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
,int(ans+0.5));
	return 0;
}