题解 P2071 【座位安排】

· · 题解

不用拆点也能过啊(ssfd) link[i][0]和link[i][1]分别表示第i排的座位匹配的人是哪个 做一次二分图就好了 常数比拆点小多了 测试点信息

1

AC 3ms/680KB

2

AC 3ms/748KB

3

AC 4ms/660KB

4

AC 3ms/636KB

5

AC 6ms/796KB

6

AC 8ms/784KB

7

AC 6ms/772KB

8

AC 9ms/796KB

9

AC 10ms/624KB

10

AC 14ms/816KB

11

AC 15ms/796KB

12

AC 3ms/800KB

13

AC 16ms/800KB

14

AC 3ms/672KB

15

AC 4ms/652KB

16

AC 3ms/628KB

17

AC 4ms/648KB

18

AC 3ms/688KB

19

AC 3ms/916KB

20

AC 3ms/644KB

跑的飞快

// luogu-judger-enable-o2

include <iostream>

include <cstdio>

include <cstdlib>

include <cstring>

include <string>

using namespace std;

const int maxn=4010;

int n,m,link[maxn>>1][2],ans;

int topt,st[maxn<<1],to[maxn<<1],nt[maxn<<2];

bool used[maxn>>1];

inline void add(int x,int y)

{to[++topt]=y; nt[topt]=st[x]; st[x]=topt;}

inline bool dfs(int x)

{

     int p=st[x];

     while (p!=-1)

     {

      if (!used[to[p]])

       {

         used[to[p]]=1;

         if (link[to[p]][0]==-1) {link[to[p]][0]=x; return 1;}

         if (link[to[p]][1]==-1) {link[to[p]][1]=x; return 1;}

         if (dfs(link[to[p]][0])) {link[to[p]][0]=x; return 1;}

         if (dfs(link[to[p]][1])) {link[to[p]][1]=x; return 1;}

        }

     p=nt[p];

     }

return 0;

}

inline int read()

{

int xx=0,ff=1; char c=getchar();

while (c<'0' || c>'9') {if (c=='-') ff=-1; c=getchar();}

while (c>='0' && c<='9') {xx=(xx<<1)+(xx<<3)+c-'0'; c=getchar();}

return xx*ff;

}

int main()

{

     n=read(); m=n<<1; register int i; 
     memset(link,-1,sizeof link);  memset(st,-1,sizeof st);
     for (i=1;i<=m;i++)
     {
       int xx,yy; xx=read(); yy=read();
       add(i,xx); add(i,yy);
     }
     for (i=1;i<=m;i++)
     {
       memset(used,0,sizeof used);
       if (dfs(i)) ans++;
     }
     printf("%d\n",ans);

return 0;

}