牛客国庆集训派对Day6 A Birthday：

 

题意：

恬恬的生日临近了。宇扬给她准备了一个蛋糕。

正如往常一样，宇扬在蛋糕上插了n支蜡烛，并把蛋糕分为m个区域。因为某种原因，他必须把第i根蜡烛插在第a

_i个区域或第b

_i个区域。区域之间是不相交的。宇扬在一个区域内同时摆放x支蜡烛就要花费x

²的时间。宇扬布置蛋糕所用的总时间是他在每个区域花的时间的和。

宇扬想快些见到恬恬，你能告诉他布置蛋糕最少需要多少时间吗？

 

思路:

　建立图，左边n个点，表示不同的蜡烛，右边m个点，表示不同的区域，根据ai和bi从左边向右边连容量为1，费用为0的边，右边每个m点都向汇点连n条边，容量为1，费用为多一个蜡烛的增量。左边还要从源点拉来容量为1，费用为0的边。

#include 
       
        #include  
        
         #include  
         
          #include   
          
           #include   
           
            #include   
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     

, greater

>que; const ll mos = 0x7FFFFFFFLL; //2147483647const ll nmos = 0x80000000LL; //-2147483648const int inf = 0x3f3f3f3f;const ll inff = 0x3f3f3f3f3f3f3f3fLL; //18const double PI=acos(-1.0); template

inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}// #define _DEBUG; //*//#ifdef _DEBUGfreopen("input", "r", stdin);// freopen("output.txt", "w", stdout);#endif/*-----------------------show time----------------------*/ const int maxn = 1e6+9; struct Edge { int to,val,cost,nxt; }gEdge[maxn]; int gHead[maxn],gPre[maxn]; int gPath[maxn],gDist[maxn]; bool in[maxn]; int gcount = 0; int n,m,k,w; int fac[maxn]; bool spfa(int s,int t){ memset(gPre, -1, sizeof(gPre)); memset(gDist,inf,sizeof(gDist)); memset(in, false , sizeof(in)); gDist[s] = 0; in[s] = true; queue

q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); in[u] = false; for(int e = gHead[u]; e!=-1; e = gEdge[e].nxt){ int v = gEdge[e].to, w = gEdge[e].cost; if(gEdge[e].val > 0 && gDist[v] > gDist[u] + w){ gDist[v] = gDist[u] + gEdge[e].cost; gPre[v] = u; gPath[v] = e; if(!in[v]){ q.push(v);in[v] = true; } } } } if(gPre[t] == -1)return false; return true; } int MinCostFlow(int s,int t){ int cost = 0,flow = 0; while(spfa(s,t)){ int f = inf; for(int u = t; u != s; u = gPre[u]){ if(gEdge[gPath[u]].val < f){ f =gEdge[gPath[u]].val; } } flow += f; cost += gDist[t] * f; for(int u=t; u!=s; u = gPre[u]){ gEdge[gPath[u]].val -= f; gEdge[gPath[u] ^ 1].val += f; } } return cost; } void addedge(int u,int v,int val, int cost){ gEdge[gcount].to = v; gEdge[gcount].val = val; gEdge[gcount].cost = cost; gEdge[gcount].nxt = gHead[u]; gHead[u] = gcount++; gEdge[gcount].to = u; gEdge[gcount].val = 0; gEdge[gcount].cost = -cost; gEdge[gcount].nxt = gHead[v]; gHead[v] = gcount++; } struct eee { int l,r,w,op; }e[maxn]; /*是大源点，m+m+1是ci源点，m+m+2是终点。 */ void solve(){ memset(gHead,-1,sizeof(gHead)); gcount = 0; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) fac[i] = i*i; for(int i=n; i>=1; i--) fac[i] = fac[i] - fac[i-1]; for(int i=1; i<=n; i++){ addedge(0,i,1,0); } for(int i=1; i<=n; i++){ int le,ri; scanf("%d%d", &le, &ri); addedge(i,le + n, 1, 0); addedge(i,ri + n, 1, 0); } for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ addedge(i+n,n+m+1,1,fac[j]); } } printf("%d\n",MinCostFlow(0,n+m+1)); } int main(){ solve(); return 0;}