想法是二分匹配 把图当作国际象棋的棋盘 黑色的点在X 白色的在Y 这样 黑白最多512个 边最多512×4   可是这样写程序不是TLE就是WA  改的很大后才AC
想知道自己哪里想错了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#define clr(a,b)    memset(a,b,sizeof(a))
using namespace std;

const int XMAX = 2000;//这两行小于2000好像就不行
const int YMAX = 2000;
const int EDGE_MAX = 4100;

struct Edge
{
    int ed,nxt;
}edge[EDGE_MAX];

int num;
int head[XMAX];
int vis[XMAX],mat[YMAX];

bool dfs(int x)
{
    vis[x] = 1;
    for(int i=head[x]; ~i; i=edge[i].nxt)
    {
        int y = edge[i].ed;
        if(vis[mat[y]] == 1)    continue;
        if(mat[y] == 0 || dfs(mat[y]))
        {
            mat[y] = x;
            return true;
        }
    }
    return false;
}

int hungary(int n)
{
    int ans = 0;
    clr(mat,0);
    for(int i=1; i<=n; i++)
    {
        clr(vis,0);
        if(dfs(i))  ans++;
    }
    return ans;
}

void addedge(int st,int ed)
{
    edge[++num].ed = ed;
    edge[num].nxt = head[st];
    head[st] = num;
}

int n,m,k;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool gra[35][35];
int id[35][35];

int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        clr(gra,false);clr(head,-1);num = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                gra[i][j] = true;

        int black = 0,white = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(((i&1)^(j&1))==0)
                    id[i][j] = ++black;
                else
                    id[i][j] = ++white;
            }

        for(int i=1; i<=k; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            gra[b][a] = false;
        }

        if((m*n-k)%2 == 1)  {printf("NO\n");continue;}
        
        int node = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(((i&1)^(j&1))==0 && gra[i][j])
                {
                    for(int p=0; p<4; p++)
                    {
                        if(gra[i+dx[p]][j+dy[p]])
                        {
                            int s=id[i][j],t=id[i+dx[p]][j+dy[p]];
                            addedge(s,t);
                            node++;
                        }
                    }
                }
            }

            if(hungary(node)*2 + k == m*n)
                printf("YES\n");
            else
                printf("NO\n");
    }
    return 0;
}

• Re:求教，询问原因。。。 (20) Fatedayt 2011-11-11 11:15:05