luogu P3324 [SDOI2015]星际战争

深碍√TFBOYSˉ_ 2021-12-03 14:39 209阅读 0赞

题面

[https://www.luogu.org/problemnew/show/P3324][https_www.luogu.org_problemnew_show_P3324]

题解

水题。

二分答案+最大流判可行。

*  注意最大流解决伤血模型的运用。

// luogu-judger-enable-o2
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue>
    #define ri register int
    #define N 505
    #define INF 1000000007
    #define T (n+m+1)
    #define eps 1e-5
    
    using namespace std;
    
    int n,m;
    vector<int> to,ed[N];
    vector<double> w;
    int cur[N],d[N];
    double sum;
    int g[N][N],a[N],b[N];
    
    inline int read() {
      int f=0,ret=0; char ch=getchar();
        while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
        while (ch>='0'&&ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar();
        return f?-ret:ret;
    }
    
    void add_edge(int u,int v,double w1,double w2) {
      to.push_back(v); w.push_back(w1); ed[u].push_back(to.size()-1);
      to.push_back(u); w.push_back(w2); ed[v].push_back(to.size()-1);
    }
    
    bool bfs() {
      queue<int> q;
      memset(d,0x3f,sizeof(d));
      d[0]=0; q.push(0);
      while (!q.empty()) {
        int x=q.front(); q.pop();
        for (ri i=0,l=ed[x].size();i<l;i++) {
          int e=ed[x][i];
          if (w[e]>eps && d[x]+1<d[to[e]]) {
            d[to[e]]=d[x]+1;
            q.push(to[e]);
          }
        }
      }
      return d[T]<=1000000;
    }
    
    double dfs(int x,double limit) {
      if (x==T || !limit) return limit;
      double tot=0;
      for (ri &i=cur[x];i<ed[x].size();i++) {
        int e=ed[x][i];
        if (d[to[e]]==d[x]+1 && w[e]>eps) {
          double f=dfs(to[e],min(limit,w[e]));
          if (f<eps) continue;
          w[e]-=f; w[1^e]+=f; 
          tot+=f; limit-=f;
          if (limit<eps) return tot;
        }
      }
      return tot;
    }
    
    double dinic() {
      double ret=0;
      while (bfs()) {
        memset(cur,0,sizeof(cur));
        ret+=dfs(0,INF);
      }
      return ret;
    }
    
    bool check(double t) {
      w.clear(); to.clear();
      for (ri i=0;i<=n+m+1;i++) ed[i].clear();
      for (ri i=1;i<=m;i++) add_edge(0,i,t*b[i],0);
      for (ri i=1;i<=n;i++) add_edge(m+i,T,a[i],0);
      for (ri i=1;i<=m;i++)
         for (ri j=1;j<=n;j++) if (g[i][j]) add_edge(i,m+j,INF,0);
      if (dinic()+eps>sum) return 1; else return 0;
    }
    
    int main() {
      n=read(); m=read();
      for (ri i=1;i<=n;i++) a[i]=read();
      sum=0.0;
      for (ri i=1;i<=n;i++) sum+=a[i];
      for (ri i=1;i<=m;i++) b[i]=read();
      for (ri i=1;i<=m;i++)
         for (ri j=1;j<=n;j++) g[i][j]=read();
      double lb=0,rb=10007; double ans=-1;
      while (rb-lb>1e-4) {
        double mid=(lb+rb)/2;
         if (check(mid)) ans=mid,rb=mid; else lb=mid;
      }
      printf("%.4lf",ans);
      return 0;
    }

转载于:https://www.cnblogs.com/shxnb666/p/11104957.html

[https_www.luogu.org_problemnew_show_P3324]: https://www.luogu.org/problemnew/show/P3324