博客

二分答案








X












$X$

设植物开始生长的时间是












x






i
















$x_i$
，结束生长的时间为











y








i















$y_i$

那么要满足以下限制

• 
  
  
  
  
  
  
  
  
  
  
  y
  
  
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  ≥
  
  
  
  
  
  x
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  $y_i\ge x_i$
• 
  
  
  
  
  
  
  
  
  
  
  y
  
  
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  ≥
  
  
  
  
  
  x
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  +
  
  
  
  
  
  t
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  −
  
  
  
  
  
  d
  
  
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  $y_i\ge x_i+t_i-d_i$
• 
  
  
  
  
  
  
  
  
  
  
  x
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  ≥
  
  
  
  
  
  y
  
  
  
  
  
  
  
  
  j
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  $x_i\ge y_j$
  （
  
  
  
  
  
  
  
  
  j
  
  
  
  
  
  
  
  
  
  
  $j$
  要在
  
  
  
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  
  
  
  
  $i$
  之前生长）
• 
  
  
  
  
  
  
  
  
  
  
  x
  
  
  
  
  
  
  t
  
  
  
  
  
  
  
  ≥
  
  
  
  
  
  y
  
  
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  $x_t\ge y_i$
• 
  
  
  
  
  
  
  
  
  
  
  x
  
  
  
  
  
  
  i
  
  
  
  
  
  
  
  ≥
  
  
  
  
  
  y
  
  
  
  
  
  
  
  
  s
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  $x_i\ge y_s$

用这个东西对欧成最大费用可行流，处理一下正权环就好了

#line 5 "Farmville.cpp"  
#include <vector>  
#include <list>  
#include <map>  
#include <set>  
#include <deque>  
#include <stack>  
#include <bitset>  
#include <algorithm>  
#include <functional>  
#include <numeric>  
#include <utility>  
#include <sstream>  
#include <iostream>  
#include <iomanip>  
#include <cstdio>  
#include <cmath>  
#include <cstdlib>  
#include <ctime>  
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

const int N=110,inf=1<<30;

int n,cst,cnt,S,T,s,t,G[N],c[N],ti[N],f[N][N];
struct edge{
  int t,nx,w,f;
}E[N*100];

#define x(i) (i<<1)
#define y(i) (i<<1|1)

ll cur;

inline void addedge(int x,int y,int f,int w){
  E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt; E[cnt].f=f; E[cnt].w=w;
  E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt; E[cnt].f=0; E[cnt].w=-w;
}

inline void link(int x,int y,int f,int w){
  if(w>0){
    cur+=1LL*f*w; addedge(S,y,f,0); addedge(x,T,f,0); addedge(y,x,f,-w);
  }
  else addedge(x,y,f,w);
}

queue<int> Q;
ll dis[N];
int vis[N],frm[N];

inline bool spfa(){
  for(int i=S;i<=T;i++) vis[i]=0,dis[i]=-inf;
  vis[S]=1; Q.push(S); dis[S]=0;
  while(!Q.empty()){
    int x=Q.front(); Q.pop(); vis[x]=0;
    for(int i=G[x];i;i=E[i].nx)
      if(E[i].f && dis[E[i].t]<dis[x]+E[i].w){
    dis[E[i].t]=dis[x]+E[i].w; frm[E[i].t]=i;
    if(!vis[E[i].t])
      vis[E[i].t]=1,Q.push(E[i].t);
      }
  }
  if(dis[T]==-inf) return false;
  int mc=inf;
  for(int i=T;i!=S;i=E[frm[i]^1].t) mc=min(mc,E[frm[i]].f);
  cur+=mc*dis[T];
  for(int i=T;i!=S;i=E[frm[i]^1].t) E[frm[i]].f-=mc,E[frm[i]^1].f+=mc;
  return true;
}

inline bool check(int X){
  cnt=1; for(int i=S;i<=T;i++) G[i]=0; cur=0;
  for(int i=1;i<=n;i++)
    link(x(i),y(i),c[i],ti[i]),link(x(i),y(i),inf,0),link(y(s),x(i),inf,0),link(y(i),x(t),inf,0);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      if(f[i][j]) link(y(j),x(i),inf,0);
  link(x(t),y(s),inf,-X);
  while(spfa());
  return cur<=cst;
}

class Farmville  
{  
public:  
  int minTime(vector <string> s, vector <int> time, vector <int> cost, int budget)  {
    n=s.size(); cst=budget; ::s=n+1; t=n+2; S=1; T=((n+2)<<1)+2;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
    if(s[i-1][j-1]=='1') f[i][j]=1; else f[i][j]=0;
    for(int i=1;i<=n;i++) ti[i]=time[i-1],c[i]=cost[i-1];
    int L=0,R=1e9,mid,ans;
    while(L<=R)
      check(mid=L+R>>1)?R=(ans=mid)-1:L=mid+1;
    return ans;
  }


};  



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor