Birthday(费用流)

Birthday

https://www.nowcoder.com/acm/contest/206/A

题目描述

恬恬的生日临近了。宇扬给她准备了一个蛋糕。
正如往常一样，宇扬在蛋糕上插了n支蜡烛，并把蛋糕分为m个区域。因为某种原因，他必须把第i根蜡烛插在第a_i个区域或第b_i个区域。区域之间是不相交的。宇扬在一个区域内同时摆放x支蜡烛就要花费x²的时间。宇扬布置蛋糕所用的总时间是他在每个区域花的时间的和。
宇扬想快些见到恬恬，你能告诉他布置蛋糕最少需要多少时间吗？

输入描述:

第一行包含两个整数n，m（1 ≤ n ≤ 50， 2≤ m≤ 50）。
接下来n行，每行两个整数a

,b

（1 ≤ a

, b

 ≤ m）。

输出描述:

一个整数表示答案。

示例1

输入

输出

示例2

输入

输出

3

把每个区域分成n份，每份的费用为i*i-(i-1)*(i-1),这是参考别人的，节点数n+m+2(两个节点之间可以连多条边)

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6  
  7 const int INF=0x3f3f3f3f;
  8 const int N=50005;
  9 const int M=500005;
 10 int top;
 11 int dist[N],pre[N];
 12 bool vis[N];
 13 int c[N];
 14 int maxflow;
 15  
 16 struct Vertex{
 17     int first;
 18 }V[N];
 19 struct Edge{
 20     int v,next;
 21     int cap,flow,cost;
 22 }E[M];
 23  
 24 void init(){
 25     memset(V,-1,sizeof(V));
 26     top=0;
 27     maxflow=0;
 28 }
 29  
 30 void add_edge(int u,int v,int c,int cost){
 31     E[top].v=v;
 32     E[top].cap=c;
 33     E[top].flow=0;
 34     E[top].cost=cost;
 35     E[top].next=V[u].first;
 36     V[u].first=top++;
 37 }
 38  
 39 void add(int u,int v,int c,int cost){
 40     add_edge(u,v,c,cost);
 41     add_edge(v,u,0,-cost);
 42 }
 43  
 44 bool SPFA(int s,int t,int n){
 45     int i,u,v;
 46     queue<int>qu;
 47     memset(vis,false,sizeof(vis));
 48     memset(c,0,sizeof(c));
 49     memset(pre,-1,sizeof(pre));
 50     for(i=1;i<=n;i++){
 51         dist[i]=INF;
 52     }
 53     vis[s]=true;
 54     c[s]++;
 55     dist[s]=0;
 56     qu.push(s);
 57     while(!qu.empty()){
 58         u=qu.front();
 59         qu.pop();
 60         vis[u]=false;
 61         for(i=V[u].first;~i;i=E[i].next){
 62             v=E[i].v;
 63             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 64                 dist[v]=dist[u]+E[i].cost;
 65                 pre[v]=i;
 66                 if(!vis[v]){
 67                     c[v]++;
 68                     qu.push(v);
 69                     vis[v]=true;
 70                     if(c[v]>n){
 71                         return false;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[t]==INF){
 78         return false;
 79     }
 80     return true;
 81 }
 82  
 83 int MCMF(int s,int t,int n){
 84     int d;
 85     int i,mincost;
 86     mincost=0;
 87     while(SPFA(s,t,n)){
 88         d=INF;
 89         for(i=pre[t];~i;i=pre[E[i^1].v]){
 90             d=min(d,E[i].cap-E[i].flow);
 91         }
 92         maxflow+=d;
 93         for(i=pre[t];~i;i=pre[E[i^1].v]){
 94             E[i].flow+=d;
 95             E[i^1].flow-=d;
 96         }
 97         mincost+=dist[t]*d;
 98     }
 99     return mincost;
100 }
101  
102 int main(){
103     int n,m;
104     int v,u,w,c;
105     int s,t;
106     cin>>n>>m;
107     init();
108     for(int i=1;i<=n;i++){
109         cin>>u>>v;
110        // for(int j=1;j<=n;j++){
111             add(i,n+u,1,0);
112        // }
113        // for(int j=1;j<=n;j++){
114             add(i,n+v,1,0);
115        // }
116     }
117     s=0,t=n+m+1;
118     for(int i=1;i<=n;i++){
119         add(s,i,1,0);
120     }
121     for(int i=1;i<=m;i++){
122         for(int j=1;j<=n;j++){
123          //   add(n+m*(i-1)+j,t,1,j*j-(j-1)*(j-1));
124             add(i+n,n+m+1,1,j*j-(j-1)*(j-1));
125         }
126     }
127     int ans=MCMF(s,t,n+m+2);
128     cout<<ans<<endl;
129 }

View Code

这是自己写的，节点数n+n*m+2

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 const int INF=0x3f3f3f3f;
  8 const int N=500005;
  9 const int M=500005;
 10 int top;
 11 int dist[N],pre[N];
 12 bool vis[N];
 13 int c[N];
 14 int maxflow;
 15 
 16 struct Vertex{
 17     int first;
 18 }V[N];
 19 struct Edge{
 20     int v,next;
 21     int cap,flow,cost;
 22 }E[M];
 23 
 24 void init(){
 25     memset(V,-1,sizeof(V));
 26     top=0;
 27     maxflow=0;
 28 }
 29 
 30 void add_edge(int u,int v,int c,int cost){
 31     E[top].v=v;
 32     E[top].cap=c;
 33     E[top].flow=0;
 34     E[top].cost=cost;
 35     E[top].next=V[u].first;
 36     V[u].first=top++;
 37 }
 38 
 39 void add(int u,int v,int c,int cost){
 40     add_edge(u,v,c,cost);
 41     add_edge(v,u,0,-cost);
 42 }
 43 
 44 bool SPFA(int s,int t,int n){
 45     int i,u,v;
 46     queue<int>qu;
 47     memset(vis,false,sizeof(vis));
 48     memset(c,0,sizeof(c));
 49     memset(pre,-1,sizeof(pre));
 50     for(i=1;i<=n;i++){
 51         dist[i]=INF;
 52     }
 53     vis[s]=true;
 54     c[s]++;
 55     dist[s]=0;
 56     qu.push(s);
 57     while(!qu.empty()){
 58         u=qu.front();
 59         qu.pop();
 60         vis[u]=false;
 61         for(i=V[u].first;~i;i=E[i].next){
 62             v=E[i].v;
 63             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 64                 dist[v]=dist[u]+E[i].cost;
 65                 pre[v]=i;
 66                 if(!vis[v]){
 67                     c[v]++;
 68                     qu.push(v);
 69                     vis[v]=true;
 70                     if(c[v]>n){
 71                         return false;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[t]==INF){
 78         return false;
 79     }
 80     return true;
 81 }
 82 
 83 int MCMF(int s,int t,int n){
 84     int d;
 85     int i,mincost;
 86     mincost=0;
 87     while(SPFA(s,t,n)){
 88         d=INF;
 89         for(i=pre[t];~i;i=pre[E[i^1].v]){
 90             d=min(d,E[i].cap-E[i].flow);
 91         }
 92         maxflow+=d;
 93         for(i=pre[t];~i;i=pre[E[i^1].v]){
 94             E[i].flow+=d;
 95             E[i^1].flow-=d;
 96         }
 97         mincost+=dist[t]*d;
 98     }
 99     return mincost;
100 }
101 
102 int main(){
103     int n,m;
104     int v,u,w,c;
105     int s,t;
106     cin>>n>>m;
107     init();
108     for(int i=1;i<=n;i++){
109         cin>>u>>v;
110         for(int j=1;j<=n;j++){
111             add(i,n+j+n*(u-1),1,0);
112             add(i,n+j+n*(v-1),1,0);
113         }
114     }
115     s=0,t=n+n*m+1;
116     for(int i=1;i<=n;i++){
117         add(s,i,1,0);
118     }
119     for(int i=1;i<=m;i++){
120         for(int j=1;j<=n;j++){
121             add(n+n*(i-1)+j,t,1,j*j-(j-1)*(j-1));
122         }
123     }
124     int ans=MCMF(s,t,n+n*m+2);
125     cout<<ans<<endl;
126 }

View Code