鏈接：swust的oj竟然沒有SPJ，做法不一樣，a不了。

題意：中文題。

分析：網絡流24題第七題。多重匹配的基礎問題，模型很簡單。

代碼：

#include<map> #include<set> #include<cmath> #include<queue> #include<bitset> #include<math.h> #include<vector> #include<string> #include<sstream> #include<stdio.h> #include<cstring> #include<iostream> #include<algorithm> #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=1050; const int MAX=1000000100; const int mod=100000000; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=998244353; const int INF=1000000010; const double pi=acos(-1.0); typedef double db; typedef unsigned long long ull; int tot,u[N],v[22*N],cap[22*N],flow[22*N],pre[22*N]; void add(int a,int b,int c,int f) {v[tot]=b;cap[tot]=c;flow[tot]=f;pre[tot]=u[a];u[a]=tot++; } bool q[2*N]; int d[2*N],dis[2*N],head[2*N]; bool bfs(int a,int b) {int i,l=1,r=1;memset(q,0,sizeof(q));d[1]=a;q[a]=1;dis[a]=0;for (;l<=r;l++)for (i=u[d[l]];i!=-1;i=pre[i])if (!q[v[i]]&&cap[i]>flow[i]) q[v[i]]=1,d[++r]=v[i],dis[v[i]]=dis[d[l]]+1;return q[b]; } int dfs(int a,int b,int en) {if (a==en||b==0) return b;int ret=0,f;for (int& i=u[a];i!=-1;i=pre[i])if (dis[v[i]]==dis[a]+1&&(f=dfs(v[i],min(b,cap[i]-flow[i]),en))>0) {flow[i]+=f;flow[i^1]-=f;ret+=f;b-=f;if (b==0) break ;}return ret; } int main() {int a,b,i,j,k,n,sum=0,ans=0;scanf("%d%d", &k, &n);tot=0;memset(u,-1,sizeof(u));for (i=1;i<=n;i++) add(0,i,1,0),add(i,0,0,0);for (i=1;i<=k;i++) {scanf("%d", &a);sum+=a;add(n+i,n+k+1,a,0);add(n+k+1,n+i,0,0);}for (i=1;i<=n;i++) {scanf("%d", &a);for (j=1;j<=a;j++) {scanf("%d", &b);add(i,n+b,1,0);add(n+b,i,0,0);}}for (i=0;i<=n+k+1;i++) head[i]=u[i];while (bfs(0,n+k+1)) {ans+=dfs(0,INF,n+k+1);for (i=0;i<=n+k+1;i++) u[i]=head[i];}if (sum!=ans) printf("No Solution!\n");else {for (i=1;i<=k;i++) {printf("%d: ", i);a=0;for (j=u[n+i];j!=-1;j=pre[j])if (flow[j]&&v[j]!=n+k+1) printf("%d ", v[j]);printf("\n");}}return 0; }

總結

以上是生活随笔為你收集整理的试题库问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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