最近真的一直在耍智障>< 一些很簡單的題目都想不太出來><
對答案作二分搜，注意到每個激光武器的攻擊量是一樣的。
所以，假設現在搜到mid，則：源點s --> 每個激光武器，流量 = t * b[i]
每個機器人 --> 匯點t，流量 = a[i]
如果激光武器 i 可以攻擊 機器人 j ，則 i-->j ，流量= a[i]
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> #include <cmath> using namespace std; #define SZ(x) ((int)(x).size()) typedef long double ld; const ld eps = 1e-9; bool eq(ld a,ld b) { return fabs(a-b) <= eps; } struct Dinic { static const int N = 106; struct Edge { int to; ld cap; int rev; Edge(){} Edge(int _to,ld _cap,int _rev) { to = _to; cap = _cap; rev = _rev; } }; vector<Edge> G[N]; void add_edge(int from,int to,ld cap) { G[from].push_back(Edge(to,cap,SZ(G[to]))); G[to].push_back(Edge(from,0,SZ(G[from])-1)); } int n,s,t; void init(int _n,int _s,int _t) { n = _n; s = _s; t = _t; for (int i=0;n>=i;i++) { G[i].clear(); } } int level[N],iter[N]; void BFS() { memset(level,-1,sizeof(level)); level[s]=0; queue<int> que; que.push(s); while (!que.empty()) { int t=que.front(); que.pop(); for (int i=0;SZ(G[t])>i;i++) { Edge e=G[t][i]; if (!eq(e.cap,0) && level[e.to] == -1) { level[e.to] = level[t] +1; que.push(e.to); } } } } ld dfs(int now, ld flow) { if (now == t) return flow; for (int &i=iter[now];SZ(G[now])>i;i++) { Edge &e = G[now][i]; if (!eq(e.cap,0) && level[e.to] == level[now] + 1) { ld ret = dfs(e.to,min(flow,e.cap)); if (!eq(ret,0)) { e.cap -= ret; G[e.to][e.rev].cap += ret; return ret; } } } return 0; } ld flow() { ld ret=0; while (true) { BFS(); if (level[t] == -1) break; memset(iter,0,sizeof(iter)); ld tmp=0; while (!eq(0, (tmp = dfs(s,1e20)) )) { ret += tmp; } } return ret; } } kirino; const int N = 56; int a[N]; int b[N]; int can[N][N]; int main () { int n,m; scanf("%d %d",&n,&m); for (int i=1;n>=i;i++) { scanf("%d",&a[i]); //robot blood } for (int i=1;m>=i;i++) { scanf("%d",&b[i]); //weapon cost } for (int i=1;m>=i;i++) { for (int j=1;n>=j;j++) { scanf("%d",&can[i][j]); //weapon i can beat robot j } } ld L=0,R=1e10; int cnt=100; int s=0,t=n+m+1; while (cnt--) { ld mid = (L+R)/2; kirino.init(t,s,t); for (int i=1;m>=i;i++) { kirino.add_edge(s,i,b[i]*mid); } ld tot=0; for (int i=1;n>=i;i++) { kirino.add_edge(i+m,t,a[i]); tot += a[i]; } for (int i=1;m>=i;i++) { for (int j=1;n>=j;j++) { if (can[i][j]) { kirino.add_edge(i,j+m,a[j]); } } } ld ret = kirino.flow(); if (eq(ret,tot)) R=mid; else L=mid; } double ans=R; printf("%.10f\n",ans); }
