• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客多校 第三场 C

admin

11月 28, 2021

当时看了眼题意,没怎么想这道题

题解比较简单,就说了求最大匹配,但是感觉实际上建图还是有点难想的

正解:
这道题实际上就是拿最小的代价去满足行与列上的最大值要求,所以实际上下面给出的点里很多都是无所谓的,关键是那些行最大值等于列最大值的点,因为他们可以同时满足两个值,以此减少整体的总和。

因此,这道题我们只需要把这些点提取出来,然后根据最大值值来做,如果某一最大值下,没有任何点可以使行列同时满足,那么要达到这些最大值只能每行每列都取一个这个值,如果有点能够把行上的该最大值和列上的最大值连接起来,那么就能减少一,所以我们根据之前存下的点产生的连接关系,对这张对于每个最大值建的二分图连接一下,然后求一个最大匹配,就能知道最多可以省下多少个最大值,然后对于每个最大值建立的图求和就行。

下附代码:

  1 #include<bits/stdc++.h>
  2 #define maxn 250
  3 #define ll long long
  4 #define INF 0x3f3f3f3f
  5 using namespace std;
  6 struct Edge {
  7     int from, to, cap, flow;
  8     Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
  9 };
 10 struct Dinic {
 11     int n, m, s, t;
 12     vector<Edge> edges;
 13     vector<int> G[maxn];
 14     int d[maxn], cur[maxn];
 15     bool vis[maxn];
 16     void init(int n) {
 17         for (int i = 0; i < n; i++) G[i].clear();
 18     edges.clear();
 19 }
 20     void AddEdge(int from, int to, int cap) {
 21         edges.push_back(Edge(from, to, cap, 0));
 22         edges.push_back(Edge(to, from, 0, 0));
 23         m = edges.size();
 24         G[from].push_back(m - 2);
 25         G[to].push_back(m - 1);
 26     }
 27     bool BFS() {
 28         memset(vis, 0, sizeof(vis));
 29         queue<int> Q;
 30         Q.push(s);
 31         d[s] = 0;
 32         vis[s] = 1;
 33         while (!Q.empty()) {
 34             int x = Q.front();
 35             Q.pop();
 36             for (int i = 0; i < G[x].size(); i++) {
 37                 Edge& e = edges[G[x][i]];
 38                 if (!vis[e.to] && e.cap > e.flow) {
 39                     vis[e.to] = 1;
 40                     d[e.to] = d[x] + 1;
 41                     Q.push(e.to);
 42                 } 
 43             }
 44         }
 45         return vis[t];
 46     }
 47     int DFS(int x, int a) {
 48         if (x == t || a == 0) return a;
 49         int flow = 0, f;
 50         for (int& i = cur[x]; i < G[x].size(); i++) {
 51             Edge& e = edges[G[x][i]];
 52             if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow)))>0){
 53                 e.flow += f;
 54                 edges[G[x][i] ^ 1].flow -= f;
 55                 flow += f;
 56                 a -= f;
 57                 if (a == 0) break;
 58             } 
 59         }
 60         return flow;
 61     }
 62     int Maxflow(int s, int t) {
 63         this->s = s;
 64         this->t = t;
 65         int flow = 0;
 66         while (BFS()) {
 67             memset(cur, 0, sizeof(cur));
 68             flow += DFS(s, INF);
 69         }
 70         return flow;
 71     }
 72 }flow;
 73 map<int,int> mph,mpl;
 74 vector<pair<int,int>> v[1000005];
 75 int a[2005],b[2005];
 76 int ch[1000005],cl[1000005];
 77 int main(){
 78     int n,m,k;
 79     scanf("%d%d%d",&n,&m,&k);
 80     for (int i=1; i<=n; i++){
 81         scanf("%d",&a[i]);
 82         ch[a[i]]++;
 83     }
 84     for (int i=1; i<=n; i++){
 85         scanf("%d",&b[i]);
 86         cl[b[i]]++;
 87     }
 88     for (int i=1; i<=m; i++){
 89         int x,y;
 90         scanf("%d%d",&x,&y);
 91         if (a[x]==b[y]){
 92             v[a[x]].push_back({x,y});
 93         }
 94     }
 95     ll res=0;
 96     for (int i=k; i>=0; i--){
 97         if (cl[i]!=0 || ch[i]!=0){
 98             mph.clear();
 99             mpl.clear();
100             flow.init(cl[i]+ch[i]+2);
101             for (int j=1; j<=ch[i]; j++){
102                 flow.AddEdge(0,j,1);
103             }
104             for (int j=1; j<=cl[i]; j++){
105                 flow.AddEdge(j+ch[i],cl[i]+ch[i]+1,1);
106             }
107             int st1=0,st2=ch[i];
108             for (int j=0; j<v[i].size(); j++){
109                 if (!mph[v[i][j].first]) mph[v[i][j].first]=++st1;
110                 if (!mpl[v[i][j].second]) mpl[v[i][j].second]=++st2;
111                 flow.AddEdge(mph[v[i][j].first],mpl[v[i][j].second],1);
112             }
113             int maxflow=flow.Maxflow(0,cl[i]+ch[i]+1);
114             res+=i*(ch[i]+cl[i]-maxflow);
115         }
116     }
117     printf("%lld",res);
118 }

View Code

发表评论

您的电子邮箱地址不会被公开。