很明显的最小费用最大流...但不是裸的..因为a*x^2不是线性关系...直接跑模板会错..例如样例的第三组数据....那么为了能做最小费用最大流..就要想办法将flow与单位费用的关系转化为线性的...
由于对于任意正整数x有x^2=1+3+5+..(2*x-1)....
那么对于a*x^2可以等价为a*(1*x+3*x+5*x+... (2*x-1)*x) = (1*a+3*a+5*a+...(2*x-1)*a)*x=1*(a*x)+3*(a*x)+5*(a*x)+..(2*x-1)*(a*x)..
而a*x是线性关系了....并且数据范围给出每个点的C最多为5也就是说拆边最多拆成5条边...所以可以拆...
比如说有条边为(s=1,e=2,a=2,c=4)将其拆成4个边: (s=1,e=2,a=2*1,c=1) (s=1,e=2,a=2*3,c=1)(s=1,e=2,a=2*5c=1)(s=1,e=2,a=2*7,c=1)
Program:
#include#include #include #include #include #include #include #define oo 1000000007 #define ll long long #define pi acos(-1.0) using namespace std; struct node { int x,y,c,a,next; }line[100005]; int N,M,K,flow,cost,_next[125],pre[125],dis[125]; queue myqueue; bool inqueue[125]; void addline(int x,int y,int num,int a,int c) { line[num].next=_next[x],_next[x]=num; line[num].x=x,line[num].y=y,line[num].a=a,line[num].c=c; return; } bool SPFA() { int x,k; while (!myqueue.empty()) myqueue.pop(); memset(pre,0,sizeof(pre)); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); myqueue.push(1); dis[1]=0; while (!myqueue.empty()) { x=myqueue.front(); myqueue.pop(); inqueue[x]=false; k=_next[x]; while (k) { if (line[k].c && dis[line[k].y]> dis[x]+line[k].a) { dis[line[k].y]=dis[x]+line[k].a; pre[line[k].y]=k; if (!inqueue[line[k].y]) { inqueue[line[k].y]=true; myqueue.push(line[k].y); } } k=line[k].next; } } if (dis[N]>oo) return false; cost=dis[N],flow=oo; x=pre[N]; while (x) { flow=min(flow,line[x].c); x=pre[line[x].x]; } x=pre[N]; while (x) { line[x].c-=flow; if (x%2) line[x+1].c+=flow; else line[x-1].c+=flow; x=pre[line[x].x]; } return true; } int MinCost_MaxFlow() { int i,MaxFlow=0,MinCost=0; while (MaxFlow