题解

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
	for(long long c;b;c=a%b,a=b,b=c);
	return a;
}
struct Fraction
{
	long long num,den;
	void simplify();
	Fraction(long long numerator,long long denominator);
	Fraction& read(); Fraction& readfrac();
	Fraction& print(); Fraction& println(); Fraction& prints();
	double getValue();
	Fraction operator+(Fraction frac); Fraction& operator+=(Fraction frac);
	Fraction operator-(Fraction frac); Fraction& operator-=(Fraction frac);
	Fraction operator*(Fraction frac); Fraction& operator*=(Fraction frac);
	Fraction operator/(Fraction frac); Fraction& operator/=(Fraction frac);
	bool operator<(Fraction frac)const; bool operator>(Fraction frac)const; bool operator<=(Fraction frac)const; bool operator>=(Fraction frac)const;
	bool operator==(Fraction frac)const; bool operator!=(Fraction frac)const;
};
void Fraction::simplify()
{
	if(den==0) den=1;
	if(den<0) den*=-1, num*=-1;
	long long g=gcd(num<0?-num:num,den);
	num/=g; den/=g;
}
Fraction::Fraction(long long numerator=0,long long denominator=1){num=numerator; den=denominator; simplify();}
Fraction& Fraction::read(){scanf("%lld",&num); den=1; return *this;}
Fraction& Fraction::readfrac(){ scanf("%lld%lld",&num,&den); simplify(); return *this;}
Fraction& Fraction::print(){printf("%lld/%lld",num,den); return *this;}
Fraction& Fraction::println(){print(); putchar('\n'); return *this;}
Fraction& Fraction::prints(){print(); putchar(' '); return *this;}
double Fraction::getValue(){return 1.0*num/den;}
Fraction Fraction::operator+(Fraction frac){Fraction ret(*this); ret+=frac; return ret;}
Fraction& Fraction::operator+=(Fraction frac){num=num*frac.den+frac.num*den; den*=frac.den; simplify(); return *this;}
Fraction Fraction::operator-(Fraction frac){Fraction ret(*this); ret-=frac; return ret;}
Fraction& Fraction::operator-=(Fraction frac){num=num*frac.den-frac.num*den; den*=frac.den; simplify(); return *this;}
Fraction Fraction::operator*(Fraction frac){Fraction ret(*this); ret*=frac; return ret;}
Fraction& Fraction::operator*=(Fraction frac){num*=frac.num; den*=frac.den; simplify(); return *this;}
Fraction Fraction::operator/(Fraction frac){Fraction ret(*this); ret/=frac; return ret;}
Fraction& Fraction::operator/=(Fraction frac){num*=frac.den; den*=frac.num; simplify(); return *this;}
bool Fraction::operator<(Fraction frac)const{return num*frac.den<frac.num*den;}
bool Fraction::operator<=(Fraction frac)const{return !(frac<*this);}
bool Fraction::operator>(Fraction frac)const{return frac<*this;}
bool Fraction::operator>=(Fraction frac)const{return !(*this<frac);}
bool Fraction::operator==(Fraction frac)const{return !(*this<frac) && !(frac<*this);}
bool Fraction::operator!=(Fraction frac)const{return !(frac==*this);}
const int N=3e3+1,M=1e6+1,K=3e2+1;
const double EPS=1e-6,FLOWEPS=1e-8;
const double INF=1e9;
struct Graph
{
	int numberOfNode,numberOfEdge;
	int head[N];
	double dis[N];
	int to[M],next[M];
	double remainingCapacity[M];
	void init(int node,int edge);
	void add(int u,int v,double c);
	void addEdge(int u,int v,double c);
	bool spfa(int s,int t);
	double dfs(int x,int t,double flow);
	double dinic(int s,int t);
	pair<Fraction,Fraction> check(double la);
};
void Graph::init(int node,int edge)
{
	for(int i=1;i<=node;i++)
	{
		head[i]=0;
	}
	numberOfNode=node;
	numberOfEdge=edge;
	return;
}
void Graph::add(int u,int v,double c)
{
	int id=++numberOfEdge;
	to[id]=v;
	next[id]=head[u];
	remainingCapacity[id]=c;
	head[u]=id;
	return;
}
void Graph::addEdge(int u,int v,double c)
{
	add(u,v,c);
	add(v,u,0);
	return;
}
bool inQueue[N];
bool Graph::spfa(int s,int t)
{
	for(int i=1;i<=numberOfNode;i++)
	{
		dis[i]=INF;
	}
	dis[s]=0;
	queue<int> q;
	q.push(s);
	for(;q.size();q.pop())
	{
		int x=q.front();
		for(int i=head[x];i;i=next[i])
		{
			if(remainingCapacity[i]>FLOWEPS && dis[to[i]]>dis[x]+1)
			{
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
		}
	}
	return dis[t]<INF;
}
double Graph::dfs(int x,int t,double flow)
{
	if(x==t)
	{
		return flow;
	}
	double getFlow=0;
	for(int i=head[x];i && flow-getFlow>FLOWEPS;i=next[i])
	{
		if(remainingCapacity[i]>FLOWEPS && dis[to[i]]==dis[x]+1)
		{
			double edgeFlow=dfs(to[i],t,min(remainingCapacity[i],flow-getFlow));
			if(edgeFlow>FLOWEPS)
			{
				getFlow+=edgeFlow;
				remainingCapacity[i]-=edgeFlow;
				remainingCapacity[i^1]+=edgeFlow;
			}
			else
			{
				dis[to[i]]=0;
			}
		}
	}
	return getFlow;
}
double Graph::dinic(int s,int t)
{
	double maxFlow=0;
	for(;spfa(s,t);)
	{
		maxFlow+=dfs(s,t,INF);
	}
	return maxFlow;
}
Graph g;
int n,m;
int a[K],b[K],c[K],d[K];
int e[K][K];
pair<Fraction,Fraction> Graph::check(double la)
{
	int s=n+m+1,t=s+1;
	init(t,1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(e[i][j])
			{
				addEdge(i,j+n,INF);
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		addEdge(i+n,t,d[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(la>b[i] && c[i])
		{
			if(a[i]==0)
			{
				addEdge(s,i,c[i]);
			}
			else
			{
				addEdge(s,i,min(1.0*c[i],(la-b[i])/2/a[i]));
			}
		}
	}
	dinic(s,t);
	Fraction kk,bb;
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==INF && b[i]<la && c[i])
		{
			if(a[i]==0 || la>2*a[i]*c[i]+b[i])
			{
				bb+=c[i];
			}
			else
			{
				kk+=Fraction(1,2*a[i]);
				bb-=Fraction(b[i],2*a[i]);
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(dis[i+n]<INF)
		{
			bb+=d[i];
		}
	}
	return make_pair(kk,bb);
}
vector<Fraction> node;
void solve(pair<Fraction,Fraction> l,pair<Fraction,Fraction> r)
{
	if(l==r)
	{
		return;
	}
	Fraction p=(r.second-l.second)/(l.first-r.first);
	pair<Fraction,Fraction> m=g.check(p.getValue()+EPS);
	if(m==r)
	{
		node.push_back(p);
	}
	else
	{
		solve(l,m);
		solve(m,r);
	}
	return;
}
void work()
{
	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]);
		}
	}
	node.push_back(0);
	for(int i=1;i<=3;i++)
	{
		solve(g.check(i-1+EPS),g.check(i-EPS));
		node.push_back(i);
	}
	solve(g.check(3+EPS),g.check(INF));
	printf("%lld\n",(long long)g.check(INF).second.getValue());
	Fraction ans;
	for(int i=1;i<node.size();i++)
	{
		Fraction x1=node[i-1],x2=node[i];
		pair<Fraction,Fraction> l=g.check(x2.getValue()-EPS),r=g.check(x2.getValue()+EPS);
		ans+=x2*((r.first-l.first)*x2+r.second-l.second);
		ans+=(x1+x2)*(x2-x1)*l.first/2;
	}
	ans.print();
	return;
}
int main()
{
	work();
    return 0;
}