題目鏈接

https://atcoder.jp/contests/agc037/tasks/agc037_d

題解

這場(chǎng)D題終于不像AGC032D和AGC036D一樣神仙了……
還是可做的吧 雖然考場(chǎng)上沒好好想賽后直接看題解了= =

考慮倒推，首先誰都能看出來第二次操作之后要讓每一行是這一行對(duì)應(yīng)元素的一個(gè)排列；
這樣的話我們可以把數(shù)\(i\)最后應(yīng)在的行視為它的顏色，第二次操作就是要把所有顏色\(i\)的數(shù)挪到第\(i\)列。
那么第一次操作之后，我們就是要讓每列是顏色的一個(gè)排列。
考慮二分圖匹配模型：
最關(guān)鍵的思路是從左往右考慮每一列
左邊對(duì)每一行建一個(gè)點(diǎn)，右邊對(duì)每種顏色建一個(gè)點(diǎn)
如果當(dāng)前還沒考慮的部分里這一行有色\(j\), 那么連邊\((i,j)\)
跑一遍Dinic確定這一行的顏色，然后下一行重復(fù)此過程
為什么這樣一定能解出來？考慮對(duì)\(M\)歸納，還剩下\(M\)行、每種顏色恰有\(M\)個(gè)的時(shí)候，對(duì)于任何行的集合\(S\), 其所包括的顏色數(shù)顯然不小于\(|S|\), 根據(jù)Hall定理，存在完美匹配，轉(zhuǎn)化為\(M-1\)的情況。
簡(jiǎn)單分析可得時(shí)間復(fù)雜度\(O(N^{3.5})\) (Dinic二分圖匹配復(fù)雜度為邊數(shù)乘以點(diǎn)數(shù)的平方根，默認(rèn)\(N,M\)同階)

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<vector> #include<algorithm> using namespace std;namespace NetFlow {const int N = 202;const int M = 40400;const int INF = 1e7;struct Edge{int v,w,nxt,rev;} e[(M<<1)+3];int fe[N+3];int te[N+3];int dep[N+3];int que[N+3];int n,en;void addedge(int u,int v,int w){ // printf("addedge%d %d %d\n",u,v,w);en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[tail] = 1; dep[1] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w>0){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[2]!=0;}int dfs(int u,int cur){if(u==2) {return cur;}int rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && e[i].w>0 && rst>0){int flow = dfs(e[i].v,min(rst,e[i].w));if(flow>0){e[i].w-=flow; e[e[i].rev].w += flow; rst-=flow;if(e[i].w>0) {te[u] = i;}if(rst==0) {return cur;}}}}if(cur==rst) {dep[u] = 0;}return cur-rst;}void dinic(int _n){n = _n;int ret = 0;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(1,INF);} // printf("ret=%d\n",ret);}void clear(){for(int i=1; i<=en; i++) e[i].v = e[i].w = e[i].nxt = e[i].rev = 0;for(int i=1; i<=n; i++) dep[i] = fe[i] = que[i] = te[i] = 0;n = en = 0;} } using NetFlow::e; using NetFlow::fe; using NetFlow::addedge; using NetFlow::dinic; using NetFlow::clear;const int N = 100; int a[N+3][N+3]; int b[N+3][N+3]; vector<int> vec[N+3][N+3]; int tmp[N+3]; int n,m;int getclr(int x) {return (x-1)/m+1;} bool cmp(int x,int y) {return getclr(x)<getclr(y);}int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&a[i][j]),vec[i][getclr(a[i][j])].push_back(a[i][j]);for(int k=1; k<=m; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(vec[i][j].size()>0) {addedge(i+2,j+n+2,1);}}addedge(1,i+2,1);addedge(i+n+2,2,1);}dinic(n+n+2);for(int i=1; i<=n; i++){int u = i+2;for(int j=fe[u]; j; j=e[j].nxt){int v = e[j].v-n-2;if(v>0 && v<=n && e[j].w==0){ // printf("(%d,%d)\n",i,v);b[i][k] = *vec[i][v].rbegin();vec[i][v].pop_back();}}}clear();}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) printf("%d ",b[i][j]); puts("");}for(int j=1; j<=m; j++){for(int i=1; i<=n; i++) tmp[i] = b[i][j];sort(tmp+1,tmp+n+1,cmp);for(int i=1; i<=n; i++) b[i][j] = tmp[i];}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) printf("%d ",b[i][j]); puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder AGC037D Sorting a Grid (二分图匹配)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。