记录编号	307567	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] 防守战线	最终得分	100
用户昵称	ceerRep	是否通过	通过
代码语言	C++	运行时间	2.390 s
提交时间	2016-09-15 15:17:55	内存使用	0.31 MiB

#include <bits/stdc++.h>
using namespace std;

namespace PROG
{
  const double inf=1e10,eps=1e-7;
  struct LP_Solver
  {
    typedef vector<double> Restrict;
    typedef vector<Restrict> Map;
    struct Infeasible {}; //无解异常
    struct Unbounded {};  //无界异常
    int cm,cn,maxid;
    vector<pair<bool,int> > pos; //编号id的变量的类型为pos[id].first,
                                 //0为非基本变量,1为基本变量
                                 //位置在pos[id].second
    Map map;
    LP_Solver(int n,int m) //n个非基本变量,m个基本变量
      :map(m+5,vector<double>(n+5,0)),cn(n),cm(m),
       pos(n+m+10),maxid(n+m)
    {
      for(int i=1;i<=n+m;i++)
	pos[i]=make_pair(i>n,i>n?i-n:i);
    }
    void Pivot(int xi,int xj)//将非基变量xj换成基变量xi
    {
      double tmp = map[xi][xj];
      int idi,idj;
      for(int i=0;i<=maxid;i++)
	if(pos[i].first == 0 && pos[i].second == xj)
	  idj=i;
	else if(pos[i].first == 1 && pos[i].second == xi)
	  idi=i;
      for(int i=0;i<=cn;i++)
	map[xi][i]/=-tmp;
      map[xi][xj]=1/tmp;
      for(int i=0;i<=cm;i++)
	{
	  tmp = map[i][xj];
	  if(i == xi) continue;
	  if(abs(tmp) < eps) continue;
	  map[i][xj]=0;
	  for(int j=0;j<=cn;j++)
	    map[i][j]+=map[xi][j]*tmp;
	}
      swap(pos[idi],pos[idj]);
    }
    double Simplex()
    {
      int xi,xj;
      double tmp;
      Init();
      while(true)
	{
	  for(xj=1;xj<=cn && map[0][xj] < eps;xj++)
	    ;
	  if(xj > cn) break;
	  tmp=inf; xi=-1;
	  for(int i=1;i<=cm;i++)
	    if(map[i][xj] < -eps && map[i][0]/-map[i][xj] < tmp)
	      tmp = map[i][0]/-map[i][xj],xi=i;
	  if(xi == -1) throw(Unbounded());
	  Pivot(xi,xj);
	}
      return map[0][0];
    }
    void Init()
    {
      int xi=-1,xj;
      double tmp=inf;
      for(int i=1;i<=cm;i++)
	if(map[i][0] < tmp)
	  tmp = map[i][0],xi = i;
      if(tmp > -eps) return;
      cn++;
      pos[0]=make_pair(0,cn);
      for(int i=1;i<=cm;i++)
	map[i][cn]=1;
      for(int j=0;j<=cn;j++)
	map[cm+1][j]=map[0][j],map[0][j]=0;
      map[0][cn]=-1;
      Pivot(xi,cn);
      Simplex();
      if(map[0][0] < -eps) throw(Infeasible());
      if(pos[0].first)
	{
	  xi=pos[0].second,xj=0;
	  while(abs(map[xi][xj]) < eps) xj++;
	  Pivot(xi,xj);
	}
      xj=pos[0].second;
      for(int i=1;i<=cm;i++)
	map[i][xj]=0;
      //替换
      for(int j=0;j<=cn;j++)
	map[0][j]=0;
      map[0][0]=map[cm+1][0];
      for(int j=1;j<=cn;j++)
	{
	  if(!pos[j].first)
	    map[0][pos[j].second]+=map[cm+1][j];
	  else
	    for(int k=0;k<=cn;k++)
	      map[0][k]+=map[cm+1][j]*map[pos[j].second][k];
	}
    }
  };
  int main(void)
  {
    freopen("zjoi13_defend.in","r",stdin);
    freopen("zjoi13_defend.out","w",stdout);
    int n,m,a,b,c;
    LP_Solver *LP;
    scanf("%d%d",&n,&m);
    LP = new LP_Solver(m,n);
    for(int i=1;i<=n;i++)
      scanf("%lf",&LP->map[i][0]);
    for(int i=1;i<=m;i++)
      {
	scanf("%d%d%d",&a,&b,&c);
	for(int j=a;j<=b;j++)
	  LP->map[j][i]=-1;
	LP->map[0][i]=c;
      }
    printf("%.0lf\n",LP->Simplex());
    return 0;
  }
}

int main(void)
{
  PROG::main();
  return 0;
}