• Wannafly camp Day1 A Birthday


    题意

      在蛋糕上插n支蜡烛,并把蛋糕分为m个区域,第i根蜡烛只能插在第ai个区域或第bi个区域,在一个区域内同时摆放x支蜡烛就要花费x2的时间。

      问摆放时间的最小值。

      n,m<=50

    题解

      很容易发现此题无法贪心,由于n和m非常小,考虑建图跑网络流。

      对于cost为参数的平方的题,可以采用拆成n个点,费用为1、3、5...具体建图为:源点向每个蛋糕连边,每个区域拆成n个点,向汇点连边,每个蛋糕向可以在的两个区域的所有点连边,第i条边的费用为2 * i - 1。跑最小费用最大流即可。

     1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 #define N 5010
     5 #define inf 0x3f3f3f3f
     6 
     7 inline int read(){
     8     int x=0,f=1;char ch=getchar();
     9     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    10     while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    11     return x*f;
    12 }
    13 
    14 int n,m,s,t,h[N],num=1,cost=0,price=0,mxflow=0;
    15 bool vis[N];
    16 struct edge{
    17     int to,next,w,c;
    18 }data[50010<<1];
    19 inline void add(int x,int y,int w,int c){
    20     data[++num].to=y;data[num].next=h[x];h[x]=num;data[num].w=w;data[num].c=c;
    21     data[++num].to=x;data[num].next=h[y];h[y]=num;data[num].w=0;data[num].c=-c;
    22 }
    23 inline int dinic(int x,int low){
    24     vis[x]=1;if(x==t){cost+=low*price;mxflow+=low;return low;}int tmp=low;
    25     for(int i=h[x];i;i=data[i].next){
    26         int y=data[i].to;if(vis[y]||!data[i].w||data[i].c) continue;
    27         int res=dinic(y,min(tmp,data[i].w));
    28         tmp-=res;data[i].w-=res;data[i^1].w+=res;
    29         if(!tmp) return low;
    30     }return low-tmp;
    31 }
    32 inline bool label(){
    33     int d=inf;
    34     for(int x=1;x<=n;++x){
    35         if(!vis[x]) continue;
    36         for(int i=h[x];i;i=data[i].next){
    37             int y=data[i].to;if(vis[y]) continue;
    38             if(data[i].w&&data[i].c<d) d=data[i].c;
    39         }
    40     }if(d==inf) return 0;
    41     for(int x=1;x<=n;++x){
    42         if(!vis[x]) continue;
    43         for(int i=h[x];i;i=data[i].next)
    44             data[i].c-=d,data[i^1].c+=d;
    45     }price+=d;return 1;
    46 }
    47 
    48 void mcmf()
    49 {
    50     do 
    51         do
    52             memset(vis,0,sizeof(vis));
    53         while(dinic(s,inf));
    54     while(label());
    55 }
    56 
    57 int main()
    58 {
    59     n = read();
    60     m = read();
    61     s = 1;
    62     t = n + n * m + 2;
    63     for (int j = 2; j <= n + 1; ++j)
    64     {
    65         int a = read(), b = read();
    66         add(s, j, 1, 0);
    67         for (int i = 1; i <= n; ++i)
    68         {
    69             add(j, n + (a - 1) * n + i + 1, 1, 2 * i - 1);
    70             add(j, n + (b - 1) * n + i + 1, 1, 2 * i - 1);
    71         }
    72     }
    73     for (int i = n + 2; i < t; ++i)
    74         add(i, t, 1, 0);
    75     n = n + n * m + 2;
    76     mcmf();
    77     printf("%d
    ", cost);
    78 
    79     return 0;
    80 }
  • 相关阅读:
    Action中使用Json
    QueryHelper插件类(hql)
    StrutsResultSupport的使用
    使用POI操作Excel
    对于response.setContentType(MIME)的解释
    通过反射技术获取泛型真实实例
    spring中context:property-placeholder
    SSH整合需要的jar包
    SSH整合主要XML代码
    设置三思LED的IP地址跟端口号
  • 原文地址:https://www.cnblogs.com/aseer/p/9459662.html
一二三 - 开发者的网上家园