网络流24题-骑士共存

题目点这里

题目or在这里

题意就略过了

现将棋盘黑白染色

建立超级源(s)和超级汇(t)

edge(s,黑,1)

edge(白,t,1)

edge(黑,白,1)

考虑s->黑->白->t的最大流

　　即最多不合法情况对

　　即最多有多少不能放

于是就变成了二分图最大匹配的板子题了

匈牙利 or Dinic

我太弱，匈牙利还不会，于是写了Dinic好像也跑得过

  1 //made by Jason_liu
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include 
 11 #include <set>
 12 using namespace std;
 13  
 14 inline void read(int &ans){
 15   ans=0;char x=getchar();int f=1;
 16   while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
 17   while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar();
 18   ans*=f;
 19 }
 20 const int MAXN=210;
 21 const int MAXV=MAXN*MAXN;
 22 const int MAXM=MAXV<<4;
 23 const int INF=2e9;
 24 struct net{int v,c,next;}E[MAXM];
 25 int n,m,head[MAXV],tot;
 26  
 27 void edge(int u,int v,int c){
 28   E[tot]=(net){v,c,head[u]},head[u]=tot++;
 29   E[tot]=(net){u,0,head[v]},head[v]=tot++;
 30 }
 31  
 32 struct Net{
 33   int s,t;
 34   int dep[MAXV],cur[MAXV];
 35   void init(int a,int b){
 36     s=a,t=b,memset(head,-1,sizeof(head));
 37   }
 38   bool bfs(){
 39     queue<int>q;
 40     memset(dep,0,sizeof(dep));
 41     q.push(s),dep[s]=1;
 42     while(!q.empty()){
 43       int u=q.front();q.pop();
 44       for(int i=head[u];~i;i=E[i].next){
 45     int v=E[i].v;
 46     if(!dep[v] && E[i].c>0){
 47       dep[v]=dep[u]+1;
 48       q.push(v);
 49     }
 50       }
 51       if(dep[t])return true;
 52     }
 53     return false;
 54   }
 55   int dfs(int u,int f){
 56     if(u==t)return f;
 57     int ans=0,cup;
 58     for(int &i=cur[u];~i;i=E[i].next){
 59       int v=E[i].v;
 60       if(E[i].c>0 && dep[v]==dep[u]+1){
 61     　　cup=dfs(v,min(f-ans,E[i].c));
 62     　　E[i].c-=cup;
 63     　　E[i^1].c+=cup;
 64     　　ans+=cup;
 65     　　if(ans==f)return ans;
 66       }
 67     }
 68     return ans;
 69   }
 70   int work(){
 71     int ans=0;
 72     while(bfs()){
 73       for(int i=0;i<=t;i++)cur[i]=head[i];
 74       ans+=dfs(s,INF);
 75     }
 76     return ans;
 77   }
 78 }a;
 79  
 80 int Tx[8]={1,1,-1,-1,2,2,-2,-2};
 81 int Ty[8]={2,-2,2,-2,1,-1,1,-1};
 82  
 83 int flag[MAXN][MAXN],cnt,x,y;
 84  
 85 int main(){
 86   //file("net");
 87   read(n),read(m);
 88   int s=n*n+1,t=s+1;a.init(s,t);
 89   for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)flag[i][j]=++cnt;
 90   for(int i=1; i<=m; i++)read(x),read(y),flag[x][y]=0;
 91   for(int i=1; i<=n; i++)
 92     for(int j=(i%2==0?2:1); j<=n; j+=2) {
 93       edge(s,flag[i][j],1);
 94         if(flag[i][j])
 95           for(int k=0; k<8; k++) {
 96             int I=i+Tx[k],J=j+Ty[k];
 97               if(I<1||J<1||I>n||J>n||!flag[I][J])continue;
 98                 edge(flag[i][j],flag[I][J],1);
 99               }
100     }
101   for(int i=1; i<=n; i++)
102     for(int j=((i%2==0)?1:2); j<=n; j+=2)
103       if(flag[i][j])
104         edge(flag[i][j],t,1);
105   printf("%d\n",n*n-m-a.work());
106   return 0;
107 }

网络流24题-骑士共存

相关

标签