[八省聯考2018]劈配?

并不難的一道題，甚至比一雙木棋還容易一些

關鍵點就是一個：怎么處理“最優結果”，即總體字典序最小

顯然要反悔。匹配問題反悔套路就多了

?

法一：

變形匈牙利算法

記錄右部點導師的戰隊情況

枚舉每個人，枚舉每一層進行嘗試匹配

最多把前面的人的邊都遍歷到，總共O(n*n*c)

?

第二問

顯然二分

第一問時候存圖即可

?

技巧：

n，m很小，充分利用桶和計數器，可以不帶set等logn結構，也不用vector（防止卡常）

#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{ const int N=201; int n,m,C; int vis[N]; int con[N][N]; int to[N][N][N],cnt[N][N]; int b[N],mem[N][N],p[N];//teacher int s[N]; int c[N];//ans1 struct node{int mem[N][N],p[N]; }tim[N]; bool dfs(int x,int d,int st){for(reg i=1;i<=cnt[x][d];++i){int y=to[x][d][i];if(vis[y]==st) continue;vis[y]=st;if(p[y]<b[y]){mem[y][++p[y]]=x;return true;}else{for(reg j=1;j<=b[y];++j){if(dfs(mem[y][j],c[mem[y][j]],st)){mem[y][j]=x;return true;}}}}return false; } void wrk1(){for(reg i=1;i<=n;++i){c[i]=m+1;memset(vis,0,sizeof vis);for(reg j=1;j<=m;++j){if(cnt[i][j]==0) continue;if(dfs(i,j,j)){c[i]=j;break;}}memcpy(tim[i].mem,mem,sizeof mem);memcpy(tim[i].p,p,sizeof p);} } bool fin(int x,int d,int t,int st){for(reg i=1;i<=cnt[x][d];++i){int y=to[x][d][i];if(vis[y]==st) continue;vis[y]=st;if(tim[t].p[y]<b[y]){return true;}else{for(reg j=1;j<=b[y];++j){if(fin(tim[t].mem[y][j],c[tim[t].mem[y][j]],t,st)){return true;}}}}return false; } bool che(int x,int t){memset(vis,0,sizeof vis);for(reg j=1;j<=s[x];++j){if(cnt[x][j]==0) continue;if(fin(x,j,t,j)) return true;}return false; } int ans[N]; void wrk2(){for(reg i=1;i<=n;++i){if(c[i]<=s[i]) {ans[i]=0;continue;}int l=0,r=i-2;int ok=-1;while(l<=r){int mid=(l+r)/2;if(che(i,mid)){ok=mid;l=mid+1;}else r=mid-1;}ans[i]=i-ok-1;} } void clear(){memset(ans,0,sizeof ans);memset(cnt,0,sizeof cnt);memset(p,0,sizeof p); } int main(){int t;rd(t);rd(C); while(t--){clear();rd(n);rd(m);for(reg i=1;i<=m;++i) rd(b[i]);for(reg i=1;i<=n;++i){for(reg j=1;j<=m;++j){rd(con[i][j]);to[i][con[i][j]][++cnt[i][con[i][j]]]=j;}}for(reg i=1;i<=n;++i){rd(s[i]);}wrk1(); // cout<<"hahaha "<<endl;for(reg i=1;i<=n;++i){printf("%d ",c[i]);}puts("");wrk2();for(reg i=1;i<=n;++i){printf("%d ",ans[i]);}puts(""); // cout<<" hahaah"<<endl; }return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/3/25 17:52:55 */ View Code

?

法二：

動態加邊dinic最大流

第一問就是把匈牙利變成dinic，據說要把匹配失敗的邊刪除防止TLE

第二問：

二分。用vector存第一問每次圖的邊

一次性把前s[i]個邊都加入，跑dinic

?

技巧：

刪除的話，只用vector.pop_back即可。其他的邊，由于找不到增廣路，所以依然流量守恒的

?

?

題面很長，實際不難

就是考察一個匹配的反悔機制了

暴力分還很多、、、

轉載于:https://www.cnblogs.com/Miracevin/p/10595837.html

總結

以上是生活随笔為你收集整理的[八省联考2018]劈配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。