#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> f;
vector<int> pre;
vector<int> a_x;
vector<int> a_y;
vector<vector<int> > c;
deque<int> q;

int bfs_1(int s,int t)
{
    f.resize(0);
    f.resize(c.size(),0);
    f[s]=oo_max;
    pre.resize(0);
    pre.resize(c.size(),-1);
    pre[s]=s;
    q.resize(0);
    for (q.push_back(s);(!q.empty())&&pre[t]==-1;q.pop_front())
    {
        int now=q.front();
        for (int i=1;i<c.size();i++)
            if (c[now][i]&&pre[i]==-1)
            {
                pre[i]=now;
                f[i]=min(c[now][i],f[now]);
                q.push_back(i);
            }
    }
    return ((pre[t]!=-1)?f[t]:-1);
}

int max_flow_1(int s,int t)
{
    int temp=0,ans=0;
    while ((temp=bfs_1(s,t))!=-1)
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][i]-=temp,c[i][pre[i]]+=temp;
        ans+=temp;
    }
    return ans;
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        a_x.resize(0);
        a_x.resize(m+1,0);
        a_y.resize(0);
        a_y.resize(m+1,0);
        for (int i=1;i<=m;i++)
        {
            int x,y;
            char c;
            scanf("%c",&c);
            scanf("%c%d",&c,&y);
            x=c-'A'+1;
            a_x[i]=x,a_y[i]=y;
        }
        c.resize(0);
        c.resize(m+2);
        for (int i=0;i<c.size();i++)
            c[i].resize(c.size(),0);
        for (int i=1;i<=m;i++)
        {
            if ((a_x[i]+a_y[i])%2==0)
            {
                c[0][i]=1;
                for (int j=1;j<=m;j++)
                    if ((a_x[j]+a_y[j])%2==1&&abs(double(a_x[i]-a_x[j]))+abs(double(a_y[i]-a_y[j]))==3&&a_x[i]!=a_x[j]&&a_y[i]!=a_y[j])
                        c[i][j]=1;
            }
            else if ((a_x[i]+a_y[i])%2==1)
                c[i][c.size()-1]=1;
        }
        printf("%d\n",max_flow_1(0,c.size()-1));
    }
}

如果骑士i与骑士j矛盾,则i,j之间连一条边.然后直接做匹配即可.
构图比较繁琐.
有没有对这个图是二分图的证明?

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/6048317.html

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<bitset>
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,x) for(int i=last[x];i!=0;i=e[i].next)
using namespace std;
#define N 30
#define M 30*30
struct edge
{
int y,next;
}e[M*3];
int last[M],ne=0;
int a[N][N],b[M][3];
int n,m;
int pri[9][3];
int l[M];
bitset<M>y;
bitset<M>z;
int lef[M];

void add(int x,int y)
{
e[++ne].y=y;e[ne].next=last[x];last[x]=ne;
}

bool match(int x)
{
efo(i,x)
if(y[e[i].y]==0)
{
y[e[i].y]=1;
if(l[e[i].y]==0||match(l[e[i].y]))
{
l[e[i].y]=x;
return 1;
}
}
return 0;
}

void build()
{
int t=0;
fo(i,-2,2)
fo(j,-2,2)
if(abs(i)!=abs(j)&&i!=0&&j!=0)
{
pri[++t][1]=i;pri[t][2]=j;
}
fo(i,1,m)
if(z[i])
{
lef[++lef[0]]=i;
fo(j,1,8)
{
int t=a[b[i][1]+pri[j][1]][b[i][2]+pri[j][2]];
if(t!=i&&t)add(i,t);
}
}
}

int main()
{
memset(a,0,sizeof(a));z.reset();
scanf("%d%d",&n,&m);
fo(i,1,m)
{
char s[5];
scanf("%s",s);
int x=s[0]-'A'+1;
int y=s[1]-'0';
if(strlen(s)>2)y=y*10+s[2]-'0';
a[x][y]=i;
b[i][1]=x;b[i][2]=y;
if((x+y)%2==1)z[i]=1;
}
build();
memset(l,0,sizeof(l));
int ans=0;
fo(i,1,lef[0])
{
y.reset();
if(match(lef[i]))ans++;
}
cout<<ans<<endl;
return 0;
}

P1729Knights
Accepted

记录信息

评测状态 Accepted
题目 P1729 Knights
递交时间 2015-07-09 01:20:50
代码语言 C++
评测机 VijosEx
消耗时间 60 ms
消耗内存 2208 KiB
评测时间 2015-07-09 01:21:03

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 2208 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2208 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 2208 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2208 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 2208 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 2204 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 2208 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 2208 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 2204 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 2208 KiB, score = 10

Accepted, time = 60 ms, mem = 2208 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n , m;
int i , j;
char s[10];
int x[700] , y[700];
int graph[700][700];
int match[700];
int use[700];
int ans;
bool black[700];

int abs( int x )
{
if( x < 0 )
return -x;
return x;
}

bool check( int xa , int ya , int xb , int yb )
{
if( abs( xa - xb ) + abs( ya - yb ) == 3 && abs( xa - xb ) != 0 && abs( ya - yb ) != 0 )
return 1;
return 0;
}

bool hungary( int x )
{
int i;
for( i = 1 ; i <= m ; i++ )
if( !use[i] && graph[x][i] )
{
use[i] = 1;
if( !match[i] || hungary( match[i] ) )
{
match[i] = x;
return 1;
}
}
return 0;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= m ; i++ )
{
scanf( "%s" , s );
x[i] = s[0] - 'A' + 1;
for( j = 1 ; s[j] != 0 ; j++ )
{
y[i] *= 10;
y[i] += s[j] - '0';
}
if( ( x[i] + y[i] ) % 2 == 0 )
black[i] = 1;
}
for( i = 1 ; i <= m ; i++ )
for( j = 1 ; j <= m ; j++ )
if( black[i] && !black[j] )
{
if( check( x[i] , y[i] , x[j] , y[j] ) )
graph[i][j] = 1;
}
else if( !black[i] && black[j] )
{
if( check( x[i] , y[i] , x[j] , y[j] ) )
graph[j][i] = 1;
}
for( i = 1 ; i <= m ; i++ )
if( black[i] )
{
memset( use , 0 , sizeof( use ) );
if( hungary( i ) )
ans++;
}
cout << ans << endl;
return 0;
}
WA了6次情何以堪

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXM 800

int n,m;

struct saver{
int x,y;
};

saver knight[MAXM];
int map[MAXM][MAXM];
bool f[MAXM][MAXM];
int sign[MAXM];

int abs(int x){
if (x<0) return -x;
return x;
}

bool check(saver x,saver y){
if (abs(x.x-y.x)==2&&abs(x.y-y.y)==1) return true;
if (abs(x.x-y.x)==1&&abs(x.y-y.y)==2) return true;
return false;
}

int flood_fill(int x,int rank){
// printf("!%d %d\n",x,rank);
sign[x]=rank;
for (int i=0;i++<m;){
if (!sign[i]&&f[x][i]){
if (rank==1) flood_fill(i,2);
else flood_fill(i,1);
}
}
return 0;
}

int h[MAXM];
int gap[MAXM];

int sap(int v,int flow){
int rec=0,minh=m+1;
if (v==m+2) return flow;
for (int i=0;i++<m+2;){
if (map[v][i]){
if (h[v]==h[i]+1){
int ret=sap(i,min(map[v][i],flow-rec));
rec+=ret;
map[v][i]-=ret;
map[i][v]+=ret;
if (flow==rec) return flow;
}
minh=min(minh,h[i]);
}
}
if (!(--gap[h[v]])){
h[m+2]=m+2;
}
h[v]=minh+1;
gap[h[v]]++;
return rec;
}

int main(){
scanf("%d%d\n",&n,&m);
for (int i=0;i<m;i++){
char c;
scanf("%c%d",&c,&knight[i].y);
knight[i].x=int(c)-int('A')+1;
if (i!=m) scanf("%c",&c);
}
memset(map,0,sizeof(map));
memset(f,0,sizeof(f));
memset(sign,0,sizeof(sign));
for (int i=0;i<m;i++){
// printf("%d %d\n",knight[i].x,knight[i].y);
for (int j=i+1;j<m;j++){
if (check(knight[i],knight[j])) {
f[i+1][j+1]=f[j+1][i+1]=true;
// printf("%d %d\n",i+1,j+1);
}
}
}
for (int i=0;i++<m;){
if (!sign[i]){
flood_fill(i,1);
}
}
for (int i=0;i++<m;){
// printf("%d\n",sign[i]);
if (sign[i]==1){
map[m+1][i]=1;
} else if (sign[i]==2) map[i][m+2]=1;
for (int j=i+1;j++<m;){
if (sign[i]==1&&sign[j]==2&&f[i][j]){
map[i][j]=0x7fffffff;
}
if (sign[i]==2&&sign[j]==1&&f[i][j]) map[j][i]=0x7fffffff;
}
}
/* for (int i=0;i++<m;){
for (int j=0;j++<m;){
printf("%d ",map[i][j]);
}
printf("\n");
}*/
memset(h,0,sizeof(h));
memset(gap,0,sizeof(gap));
gap[0]=m+2;
int ans=0;
while (h[m+1]<m+2){
ans+=sap(m+1,0x7fffffff);
}
printf("%d\n",ans);
return 0;
}

无奈网络流秒不了~~55
上海红茶馆 - Windows Server 2003 via JudgeDaemon2/13.5.1.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 3392 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 3388 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 3384 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
Accepted, time = 93 ms, mem = 3392 KiB, score = 100

二分图最大独立集=二分图点数-最大匹配数

所以所求即为最大匹配数。

很裸的二分图匹配