题解

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct frac {
	ll x,y;
	frac(ll a=0,ll b=1) { ll d=__gcd(a,b); x=a/d,y=b/d; }
	friend bool operator==(const frac &u,const frac &v) {
		return u.x*v.y==u.y*v.x;
	}
	friend frac operator +(const frac &u,const frac &v) {
		return frac(u.x*v.y+u.y*v.x,u.y*v.y);
	}
	friend frac operator -(const frac &u,const frac &v) {
		return frac(u.x*v.y-u.y*v.x,u.y*v.y);
	}
	friend frac operator *(const frac &u,const frac &v) {
		return frac(u.x*v.x,u.y*v.y);
	}
	friend frac operator /(const frac &u,const frac &v) {
		return frac(u.x*v.y,u.y*v.x);
	}
	double eval() { return 1.*x/y; }
};

struct line {
	frac k,b;
	frac f(frac x) { return x*k+b; }
	friend bool operator ==(const line &u,const line &v) {
		return u.k==v.k&&u.b==v.b;
	}
};

namespace Flow {
const int MAXV=205,MAXE=1e5+5,inf=1e9;
const double eps=1e-8;
int S,T,ecnt,hd[MAXV],dep[MAXV],cur[MAXV];
struct Edge {
	int v,lst; double f;
}	G[MAXE];
void init() { ecnt=1,memset(hd,0,sizeof(hd)); }
void adde(int u,int v,double w) { G[++ecnt]={v,hd[u],w},hd[u]=ecnt; }
void link(int u,int v,double w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
	memset(dep,-1,sizeof(dep));
	memcpy(cur,hd,sizeof(cur));
	queue <int> Q; Q.push(S),dep[S]=0;
	while(Q.size()) {
		int u=Q.front(); Q.pop();
		for(int i=hd[u];i;i=G[i].lst) if(dep[G[i].v]==-1&&G[i].f>eps) {
			dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
		}
	}
	return ~dep[T];
}
double dfs(int u,double f) {
	if(u==T||f<eps) return f;
	double r=f;
	for(int i=cur[u];i;i=G[i].lst) {
		int v=G[i].v; cur[u]=i;
		if(dep[v]==dep[u]+1) {
			double g=dfs(v,min(r,G[i].f));
			G[i].f-=g,r-=g,G[i^1].f+=g;
		}
		if(r<eps) return f;
	}
	return f-r;
}
void maxflow() { while(BFS()) dfs(S,inf); }
}
const int MAXN=105,inf=1e9;
const double eps=1e-7;
int n,m,a[MAXN],b[MAXN],c[MAXN],d[MAXN],e[MAXN][MAXN];
line flow(double k) {
	Flow::init();
	int S=Flow::S=n+m+1,T=Flow::T=n+m+2;
	for(int i=1;i<=n;++i) if(k>b[i]) {
		if(!a[i]) Flow::link(S,i,c[i]);
		else Flow::link(S,i,min((k-b[i])/2/a[i],1.*c[i]));
	}
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(e[i][j]) Flow::link(i,j+n,inf);
	for(int i=1;i<=m;++i) Flow::link(i+n,T,d[i]);
	Flow::maxflow();
	line f;
	for(int i=1;i<=n;++i) if(k>b[i]&&Flow::dep[i]==-1) {
		if(2*a[i]*c[i]+b[i]<k) f.b=f.b+c[i]; //full in real network
		else f.k=f.k+frac(1,2*a[i]),f.b=f.b-frac(b[i],2*a[i]); //not full in real network
	}
	for(int i=1;i<=m;++i) if(~Flow::dep[i+n]) f.b=f.b+d[i];
	return f;
}
vector <frac> g; //changing points
void conv(line l,line r) {
	if(l==r) return ;
	frac k=(r.b-l.b)/(l.k-r.k);
	line mid=flow(k.eval()+eps);
	if(mid==r) g.push_back(k);
	else conv(l,mid),conv(mid,r);
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(int i=1;i<=m;++i) scanf("%d",&d[i]);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&e[i][j]);
	printf("%d\n",(int)flow(inf).b.eval());
	g.push_back(0);
	for(int k:{1,2,3}) conv(flow(k-1+eps),flow(k-eps)),g.push_back(k);
	conv(flow(3+eps),flow(inf));
	frac ans=0;
	for(int i=1;i<(int)g.size();++i) {
		line l=flow(g[i].eval()-eps),r=flow(g[i].eval()+eps);
		ans=ans+g[i]*(r.f(g[i])-l.f(g[i])); 
		ans=ans+(g[i]+g[i-1])*(l.f(g[i])-l.f(g[i-1]))/2; 
    }
	printf("%lld/%lld\n",ans.x,ans.y);
	return 0;
}