[loj2477]劈配

考虑依次选择每一位考生，设当前选到第$i+1$位，前i个分别为$p1,p2,……pi$（注意：这里只确定了导师的志愿编号），然后枚举第$p_{i+1}$，通过网络流建图+判定，复杂度为$o(nm*f(n+m,cn))$（$f(n,m)$表示点数为n、边数为m的网络流），无法通过

考虑优化，由于网络流可以先任意流，那么直接在之前的残余网络上加上第k份志愿并判断能否联通即可，复杂度$o(cn^{2}m)$

第二个问题类似，存储下每一次跑完后的残余网络，然后从下往上枚举其排名（志愿为si及其以上的）并建图，复杂度同样为$o(cn^{2}m)$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 205

 4 struct ji{

 5     int nex,to,len;

 6 }edge[30*N],e[N][30*N];

 7 vector<int>v[N][N];

 8 int E,t,n,m,x,EE[N],head[N<<1],vis[N<<1],h[N][N<<1];

 9 void add(int x,int y,int z){

10     edge[E].nex=head[x];

11     edge[E].to=y;

12     edge[E].len=z;

13     head[x]=E++;

14 }

15 bool dfs(int k){

16     if (k==n+m+1)return 1;

17     if (vis[k])return 0;

18     vis[k]=1;

19     for(int i=head[k];i!=-1;i=edge[i].nex)

20         if ((edge[i].len)&&(dfs(edge[i].to))){

21             edge[i].len--;

22             edge[i^1].len++;

23             return 1;

24         }

25     return 0;

26 }

27 int main(){

28     scanf("%d%*d",&t);

29     while (t--){

30         scanf("%d%d",&n,&m);

31         E=0;

32         memset(head,-1,sizeof(head));

33         for(int i=1;i<=n;i++)

34             for(int j=1;j<=m;j++)v[i][j].clear();

35         for(int i=1;i<=m;i++){

36             scanf("%d",&x);

37             add(i+n,n+m+1,x);

38             add(n+m+1,i+n,0);

39         }

40         for(int i=1;i<=n;i++)

41             for(int j=1;j<=m;j++){

42                 scanf("%d",&x);

43                 if (x)v[i][x].push_back(j);

44             }

45         EE[0]=E;

46         memcpy(h[0],head,sizeof(head));

47         memcpy(e[0],edge,sizeof(edge));

48         for(int i=1;i<=n;i++){

49             bool flag=0;

50             EE[i]=E;

51             memcpy(h[i],head,sizeof(head));

52             memcpy(e[i],edge,sizeof(edge));

53             for(int j=1;j<=m;j++){

54                 E=EE[i];

55                 memset(vis,0,sizeof(vis));

56                 memcpy(head,h[i],sizeof(head));

57                 memcpy(edge,e[i],sizeof(edge));

58                 for(int k=0;k<v[i][j].size();k++){

59                     add(i,v[i][j][k]+n,1);

60                     add(v[i][j][k]+n,i,0);

61                 }

62                 if (dfs(i)){

63                     flag=1;

64                     printf("%d ",j);

65                     break;

66                 }

67             }

68             if (!flag)printf("%d ",m+1);

69             EE[i]=E;

70             memcpy(h[i],head,sizeof(head));

71             memcpy(e[i],edge,sizeof(edge));

72         }

73         printf("\n");

74         for(int i=1;i<=n;i++){

75             scanf("%d",&x);

76             bool flag=0;

77             for(int j=i;j;j--){

78                 E=EE[j-1];

79                 memset(vis,0,sizeof(vis));

80                 memcpy(head,h[j-1],sizeof(head));

81                 memcpy(edge,e[j-1],sizeof(edge));

82                 for(int k=1;k<=x;k++)

83                     for(int l=0;l<v[i][k].size();l++){

84                         add(i,v[i][k][l]+n,1);

85                         add(v[i][k][l]+n,i,0);

86                     }

87                 if (dfs(i)){

88                     flag=1;

89                     printf("%d ",i-j);

90                     break;

91                 }

92             }

93             if (!flag)printf("%d ",i);

94         }

95         printf("\n");

96     }

97 }

巴特西

[loj2477]劈配

最新文章

热门文章