Description

Input

Output

輸出到文件 mentor.out 中。
按順序輸出每組數據的答案。對于每組數據，輸出 2 行：
? 第 1 行輸出 n 個用空格隔開的正整數，其中第 i 個整數的意義為：
– 在最優的錄取方案中，編號為 i 的選手會被該檔志愿錄取。
– 特別地，如果該選手出局，則這個數為 m + 1。
? 第 2 行輸出 n 個用空格隔開的非負整數，其中第 i 個整數的意義為：
– 使編號為 i 的選手不沮喪，最少需要讓他上升的排名數。
– 特別地，如果該選手一定會沮喪，則這個數為 i。

Sample Input

輸入1：

3 5
2 2
1 1
2 2
1 2
1 1
2 2
1 1
1 2
1 2
2 1
2 2
1 1
0 1
0 1
2 2

輸入2：

1 5
4 3
2 1 1
3 1 3
0 0 1
3 1 2
2 3 1
2 3 3 3

Sample Output

輸出1：

2 1
1 0
1 2
0 1
1 3
0 1

【樣例 1 解釋】

三組數據分別與【題目描述】中的三個表格對應。
對于第 1 組數據：由于選手 1 沒有填寫第一志愿，所以他一定無法被第一志愿錄
取，也就一定會沮喪。選手 2 按原排名就不沮喪，因此他不需要提升排名。
對于第 2 組和第 3 組數據：1 號選手都不需要提升排名。而希望被第一志愿錄取的
2 號選手都必須升到第 1 名才能如愿。

輸出2：

1 1 3 2
0 0 0 0

【樣例 2 解釋】

1 號選手的第一志愿只填寫了 2 號導師，因此 1 號選手必定被 2 號導師錄取。
2 號選手的第一志愿只填寫了 3 號導師，因此 2 號選手必定被 3 號導師錄取。
由于 2,3 號導師均滿員，且 3,4 號選手均填寫了 1 號導師，因此它們都會被 1 號導
師錄取。
所以 1,2 號選手均被第 1 志愿錄取，3 號選手被第 3 志愿錄取，4 號選手被第 2 志
愿錄取。
由于他們都如愿以償了，所以他們都不需要提升名次。

Data Constraint

Solution

• 題面真的很長……

• 一看數據范圍 n,m≤200，嗯，網絡流。

• 由于每次都是最優方案，所以最終每個人選的志愿都是唯一固定的。

• 我們只需要知道他們到底選了哪個志愿，不需要知道具體選了哪個老師。

• 題目有兩個問，考慮先做第一個問。

• 假設前 i?1 個人已經處理完了，現在要求出第 i 個人的最優志愿 f[i]。

• 考慮 二分 這第 i 個人最好能選第幾志愿，設為 mid ，接著判斷 i 能否選志愿 mid 。

• 具體方法：建源匯點 s,t ，s 向 1 到 i 各連一條容量為 1 的邊，

• 之后每位導師 j 向 t 各連一條容量為 b[j] 的邊。

• 然后 1 到 i?1 按照之前處理好的志愿向對應的第 f[] 志愿的導師連容量為 1 的邊。

• 最后 i 向其第 mid 志愿的每個老師都連一條容量為 1 的邊即可。

• 每次暴力建圖，跑一遍最大流，算出最大流量 sum ，這個流量就代表著有 sum 個人選了志愿。

• 那么如何判斷二分的這個 mid 可行呢？

• 我們可以記錄一個 pre[i] ，表示前 i 個人按照最優方案執行后 沒出局的人數。

• 如果滿足：pre[i?1]+1=sum 即為滿足（即第 i 個人成功選上了）。

• 這樣我們就二分出了最優的 mid ，更新 f[i] 即可。

• 于是我們就求出了第一問的答案 f[i] ，先算算時間復雜度：

• 先枚舉每個人 i O(N)，在二分選志愿 O(log?N) ，做網絡流復雜度設為 C 。

• 那么總時間復雜度就是 O(NC logN) ，額，能過。

• 那我們愉快地再來做第二問。

• 仍然是考慮二分，對于第 i 個人，二分他要到哪個位置，設為 mid 。

• 這是我們還是可以利用之前算出的 f[i] ：將 1 到 mid?1 都按照 f 的志愿連邊（同上）。

• 源匯點 s,t 的連邊方式也一樣，不同的是點 mid 的連邊。

• 由于我們只需要判斷位置 mid 對于第 i 個人是否可行（不需要具體求出其選什么志愿），

• 所以我們直接將 mid 向 1 到 s[i] 各連一條容量為 1 的邊，表示在其中任選一個志愿即可。

• 判斷也和之前一樣，滿足：pre[mid?1]+1=sum 即為符合，更新答案即可。

• 分析一下復雜度，枚舉每個人 O(N) ，二分選在哪 O(log?N) ，之后又做網絡流 C 。

• 復雜度還是 O(NC logN) ！于是總時間復雜度就是 O(NC?logN) ，能過本題。

Code

#include<cstdio> #include<cstring> #include<vector> #include<cctype> using namespace std; const int N=205,M=N<<1,inf=1e9; int n,m,s,t,tot; int first[M],nex[M*M],en[M*M],w[M*M]; int b[N],ss[N],f[N],pre[N]; int dis[M],gap[M],cur[M]; vector<int>g[N][N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void ins(int x,int y,int z) {nex[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void insert(int x,int y,int z) {ins(x,y,z),ins(y,x,0); } int sap(int x,int y) {if(x==t) return y;int use=0;for(int i=cur[x];i;i=nex[i])if(w[i] && dis[x]==dis[en[i]]+1){cur[x]=i;int num=sap(en[i],min(w[i],y-use));w[i]-=num,w[i^1]+=num,use+=num;if(use==y || dis[s]>t) return use;}cur[x]=first[x];if(!--gap[dis[x]]) dis[s]=t+1;gap[++dis[x]]++;return use; } inline bool check(int ii,int pos) {tot=1;memset(first,0,sizeof(first));for(int i=1;i<=ii;i++) insert(s,i,1);for(int i=1;i<=m;i++) insert(n+i,t,b[i]);for(int i=1;i<ii;i++)if(f[i]<=m)for(int j=0;j<g[i][f[i]].size();j++) insert(i,n+g[i][f[i]][j],1);for(int j=1;j<=pos;j++)for(int i=0;i<g[ii][j].size();i++) insert(ii,n+g[ii][j][i],1);for(int i=1;i<=t;i++) cur[i]=first[i];memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));gap[0]=t;int sum=0;while(dis[s]<=t) sum+=sap(s,inf);return sum==pre[ii-1]+1; } inline bool check1(int ii,int nn) {tot=1;memset(first,0,sizeof(first));for(int i=1;i<nn;i++) insert(s,i,1);insert(s,ii,1);for(int i=1;i<=m;i++) insert(n+i,t,b[i]);for(int i=1;i<nn;i++)if(f[i]<=m)for(int j=0;j<g[i][f[i]].size();j++) insert(i,n+g[i][f[i]][j],1);for(int i=1;i<=ss[ii];i++)for(int j=0;j<g[ii][i].size();j++) insert(ii,n+g[ii][i][j],1);for(int i=1;i<=t;i++) cur[i]=first[i];memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));gap[0]=t;int sum=0;while(dis[s]<=t) sum+=sap(s,inf);return sum==pre[nn-1]+1; } int main() {int T=read(),c=read();while(T--){n=read(),m=read();for(int i=1;i<=m;i++) b[i]=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) g[i][j].clear();for(int j=1,x;j<=m;j++)if(x=read()) g[i][x].push_back(j);}for(int i=1;i<=n;i++) ss[i]=read();s=n+m+1,t=n+m+2;for(int i=1;i<=n;i++){int l=1,r=m;f[i]=m+1;while(l<=r){int mid=l+r>>1;if(check(i,mid)){f[i]=mid;r=mid-1;}else l=mid+1;}write(f[i]),putchar(' ');pre[i]=pre[i-1]+(f[i]<=m);}putchar('\n');for(int i=1;i<=n;i++){if(f[i]<=ss[i]){putchar('0'),putchar(' ');continue;}int l=1,r=i-1,pos=0;while(l<=r){int mid=l+r>>1;if(check1(i,mid)){pos=mid;l=mid+1;}else r=mid-1;}write(i-pos),putchar(' ');}putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5640. 【NOI2018模拟4.9】劈配的全部內容，希望文章能夠幫你解決所遇到的問題。

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