Problem:1022 新建题解

Solution_ID:32846            覆盖(二分图)

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int qx[2]={-1,0},qy[2]={0,-1};
int n,m,id1=0,id2=0,match[5009],w[5009][5009],k;
bool a[5009][5009],map[5009][5009],use[5009];
bool dfs(int i)
{
if (use[i]) return false;
use[i]=true;
for (int j=1;j<=id2;j++)
if (a[i][j])
if (!match[j]||dfs(match[j]))
{
match[j]=i;
return true;
}
return false;
}
int work()
{
int ans=0;
for (int i=1;i<=id1;i++)
{
memset(use,false,sizeof(use));
if (dfs(i)) ans++;
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int x,y;
for (int i=1;i<=k;i++) scanf("%d%d",&x,&y),map[x][y]=true;

for (int i=0;i<=n+1;i++) map[i][0]=map[i][m+1]=true;
for (int i=0;i<=m+1;i++) map[0][i]=map[n+1][i]=true;

for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!map[i][j])
{
if((i+j)&1)
{
w[i][j]=++id1;
for (int l=0;l<2;l++) if (!map[i+qx[l]][j+qy[l]]) a[id1][w[i+qx[l]][j+qy[l]]]=true;
}
else
{
w[i][j]=++id2;
for (int l=0;l<2;l++) if (!map[i+qx[l]][j+qy[l]]) a[w[i+qx[l]][j+qy[l]]][id2]=true;
}
}
printf("%d",work());
return 0;
}


by 92715 七月 6, 2019, 1:29 p.m.

Solution_ID:28025            二分图经典题

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int qx[2]={-1,0},qy[2]={0,-1};

int n,m,id1=0,id2=0,match[5009],w[5009][5009],k;

bool a[5009][5009],map[5009][5009],use[5009];

bool dfs(int i) 

{

if (use[i]) return false;

use[i]=true;

for (int j=1;j<=id2;j++)

if (a[i][j])

if (!match[j]||dfs(match[j]))

{

match[j]=i;

return true;

}

return false;

}

int work()

{

int ans=0;

for (int i=1;i<=id1;i++)

{

memset(use,false,sizeof(use));

if (dfs(i)) ans++;

}

return ans;

}

int main()

{

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

int x,y;

for (int i=1;i<=k;i++) scanf("%d%d",&x,&y),map[x][y]=true;


for (int i=0;i<=n+1;i++) map[i][0]=map[i][m+1]=true;

for (int i=0;i<=m+1;i++) map[0][i]=map[n+1][i]=true;

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

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

if (!map[i][j])

{

if((i+j)&1) 

{

w[i][j]=++id1;

for (int l=0;l<2;l++) if (!map[i+qx[l]][j+qy[l]]) a[id1][w[i+qx[l]][j+qy[l]]]=true;

}

else 

{

w[i][j]=++id2;

for (int l=0;l<2;l++) if (!map[i+qx[l]][j+qy[l]]) a[w[i+qx[l]][j+qy[l]]][id2]=true;

}

}

printf("%d",work());

return 0;

}


by 41988 七月 18, 2017, 4:57 p.m.

Solution_ID:27288            发现楼下题解有一个错的呀

                   时间复杂度:Θ(O(n^4)) 空间复杂度:Θ(O(n^2))

@by 36918的题解

您的做法有显然的错误,附反例数据

Input:

3 6 

8

1 1

3 1

1 3

3 3

1 4

3 4

1 6

3 6

Answer:3

Your Output:5

我不知道其他染色的做法有没有错误,于是自己写一篇以便后人鉴别好了

首先,考虑如果将方格图黑白染色(每个格子的相邻格子颜色与自身相反,暂时将障碍点也染色),那么方格图变为5000+5000点的二分图

相邻黑格白格若没有障碍点即可以连边,不能互相覆盖对应每个点只能连一条边,于是这是一个经典二分图最大匹配模型

实现的时候可以不用把边存起来,跑增广路算法的时候直接枚举方向即可

复杂度分析:点数O(n^2), 边数O(n^2),还是可以过的

代码如下

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 103

int dx[4]={1,-1,0,0};

int dy[4]={0,0,1,-1};

int match[maxn][maxn][2];

bool vzt[maxn][maxn];

bool gg[maxn][maxn];

int n,m,k;

int ans;

bool dfs(int *u)

{

    vzt[u[0]][u[1]]=true;

    for(int i=0;i<4;i++)

    {

        int vx=u[0]+dx[i];

        int vy=u[1]+dy[i];

        if(vx<1||vx>n||vy<1||vy>m||vzt[vx][vy]||gg[vx][vy])

            continue;

        vzt[vx][vy]=true;

        if(!match[vx][vy][0]||dfs(match[vx][vy]))

        {

            match[vx][vy][0]=u[0];

            match[vx][vy][1]=u[1];

            return true;

        }

    }

    return false;

}            

int main()

{

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

    scanf("%d",&k);

    for(int i=1;i<=k;i++)

    {

        int x,y;

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

        gg[x][y]=true;

    }

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

        for(int j=(i&1)+1;j<=m;j+=2)

            if(!gg[i][j])

            {

                int a[2];

                a[0]=i,a[1]=j;

                memset(vzt,0,sizeof(vzt));

                if(dfs(a)) ans++;

            }

    printf("%d",ans);

    return 0;

}


                

            


by 14041 六月 16, 2017, 3:32 p.m.

Solution_ID:26163            覆盖,简单算

                   时间复杂度:Θ() 空间复杂度:Θ()

这里写题解


# include <stdio.h>
int main (void)
{
    int p[100][100]={0};//创建地图 赋值0 为陆地
    int n , m , k ;
    int sum=0,a,b,i,j;
    scanf("%d %d",&n,&m);
    scanf("%d",&k);
    for(i=0;i<k;i++)//创建地图上的水塘赋值-1
    {
        scanf("%d %d",&a,&b);
        p[a][b]=-1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(p[i][j]==0 )//找到陆地 分情况覆盖 以横向为主 纵向为辅助 并改变其值为1
            {
                if(j+1<=m && p[i][j+1]==0)
                {
                    p[i][j]=1;
                    p[i][j+1]=1;
                    sum++;
                }
                else if(i+1<=n && p[i+1][j]==0)
                {
                    p[i][j]=1;
                    p[i+1][j]=1;
                    sum++;
                }
               
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}


by 55585 四月 6, 2017, 10:47 a.m.

Solution_ID:24916            【二分图开始涂色啦】

                   时间复杂度:Θ(n) 空间复杂度:Θ(n*m)

CODE:

#include<bits/stdc++.h>
#define go(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,k,cnt,ans=0,M[105][105],color[105*105][3];
void dfs(int CO,int x,int y){
    if(M[x][y]<0)return;if(!M[x][y]){
	   color[cnt][M[x][y]=CO]++;
       go(i,0,3){int X=x+dx[i],Y=y+dy[i];
       if(X>0&&Y>0&&X<=n&&Y<=m) if(!M[X][Y])dfs(3-CO,X,Y);}}}
int main(){
   int x,y;scanf("%d%d%d",&n,&m,&k);
   go(i,1,k)scanf("%d%d",&x,&y),M[x][y]=-1;
   go(i,1,n)go(j,1,m)if(!M[i][j])cnt++,dfs(1,i,j);
   go(i,1,cnt)ans+=min(color[i][1],color[i][2]);
   printf("%d\n",ans);return 0;}//Paul_Guderian

by 25737 二月 8, 2017, 9:10 p.m.

Solution_ID:24078            暴力建图不可取 = =

                   时间复杂度:Θ(不知道= =) 空间复杂度:Θ(o(n^2))

const xx:array[1..4] of longint=(1,0,-1,0);

      yy:array[1..4] of longint=(0,1,0,-1);

var   black,white,res,q1,q2,q3:array[1..10000] of longint;

      state:array[1..10000] of boolean;

      a,map:array[0..105,0..105] of boolean;

      color,co:array[0..105,0..105] of longint;

      i,j,k,p,q,n,m,w,b,f,l,ans,ii,jj:longint;


  function dfs(k:longint):boolean;

    var i,j,n:longint;

    begin

        for i:=1 to w do

           if (state[white[i]]=false) and  (a[k,white[i]]) then  begin

             state[white[i]]:=true;

             if (res[white[i]]=0)  or (dfs(res[white[i]])) then begin

                res[white[i]]:=k;    exit(true);

             end;

           end;

        exit(false);

    end;

 

 begin

     readln(n,m);

     readln(k);

     fillchar(map,sizeof(map),false);

     for i:=1 to n do

      for j:=1 to m do map[i,j]:=true;

     for i:=1 to k do begin

       readln(p,q);

       map[p,q]:=false;

     end;


     for i:=1 to n do

       for j:=1 to m do

         if map[i,j] then begin

            f:=0; l:=1; b:=0; w:=0;

            fillchar(res,sizeof(res),0);fillchar(state,sizeof(state),false);

            fillchar(a,sizeof(a),false);  fillchar(color,sizeof(color),0);

            q1[1]:=i; q2[1]:=j; q3[1]:=1; {black}

            inc(b); black[1]:=1; map[i,j]:=false;

            color[i,j]:=1;

            co[i,j]:=1;

            while f<l do begin

              inc(f);

              for k:=1 to 4 do

                if map[q1[f]+xx[k],q2[f]+yy[k]] then begin

                   inc(l);

                   map[q1[f]+xx[k],q2[f]+yy[k]]:=false;

                   q1[l]:=q1[f]+xx[k];

                   q2[l]:=q2[f]+yy[k];

                   if q3[f]=1 then begin

                     q3[l]:=0;

                     inc(w);

                     white[w]:=l;

                     color[q1[l],q2[l]]:=l;

                     co[q1[l],q2[l]]:=2;

                   end


                   else begin

                     q3[l]:=1;

                     inc(b);

                     black[b]:=l;

                     color[q1[f]+xx[k],q2[f]+yy[k]]:=l;

                     co[q1[l],q2[l]]:=1;

                   end;

                end;

              end;


       for ii:=1 to n do

         for jj:=1 to m do

           if co[ii,jj]=1 then

            for p:=1 to  4 do

             if co[ii+xx[p],jj+yy[p]]=2 then

               a[color[ii,jj],color[ii+xx[p],jj+yy[p]]]:=true;



       for p:=1 to b do if dfs(black[p]) then inc(ans);

     end;


       writeln(ans);

     end.


by 48891 十二月 21, 2016, 8:33 p.m.

Solution_ID:22098            二分图染色

                   时间复杂度:Θ(O(nm)) 空间复杂度:Θ(O(nm))

  • 很容易发现这是一个二分图,然后对每个连通块进行染色,思考后发现,对于每个连通块,答案为min(color1,color2),将所有连通块的答案统计起来即可 


  • #include <iostream>
  • #include <cstdio>
  • #include <algorithm>

using namespace std;

const int N=110,M=110;

int n,m,k,cnt,ans=0;

int G[N][M];

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int color[N*M][3];

void dfs(int clr,int x,int y) {

if (G[x][y]<0) return;

if (!G[x][y]) {

G[x][y]=clr;

color[cnt][clr]++;

for (int i=0;i<4;i++) {

int nx=x+dx[i],ny=y+dy[i];

if (nx>0&&ny>0&&nx<=n&&ny<=m) 

if (G[nx][ny]==0) 

dfs(3-clr,nx,ny);

}

}

}

int main(){

cin>>n>>m>>k;

for (int i=1;i<=k;i++) {

int x,y;

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

G[x][y]=-1;

}

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

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

if (G[i][j]==0) {

cnt++;

dfs(1,i,j);

}

}

for (int i=1;i<=cnt;i++) ans+=min(color[i][1],color[i][2]);

cout<<ans<<endl;

return 0;

}


by 36918 十月 11, 2016, 9:50 p.m.

Solution_ID:20894            白痴建图法

                   时间复杂度:Θ(Xi_Jinping 拿到Au) 空间复杂度:Θ(BJLFZS2 AC了题库)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define INF 1000000007
#define maxn 10010
#define maxs 110
using namespace std;
struct edge{
    int next,to,cap,flow;
}e[maxn];
bool b[maxs][maxs];
int temp = 1;
int first[maxn],q[maxn],d[maxn];
int si[maxn][maxn];
bool vis[maxn];
int s,t,n,m,k,tot = 1;
void add(int x,int y,int z){
    e[++tot].to = y;
    e[tot].cap = z;
    e[tot].next = first[x];
    first[x] = tot;
}
bool bfs(){
    int head = 0,tail = 1;
    memset(vis,0,sizeof(vis));
    q[1] = s;    vis[s] = 1;    d[s] = 1;
    while (tail > head){
        int x = q[++head];
        for (int i = first[x]; i; i = e[i].next){
            int v = e[i].to;
            if (!vis[v] && e[i].cap > e[i].flow){
                q[++tail] = v;
                vis[v] = 1;
                d[v] = d[x] + 1;
                if (v == t)    return 1;
            }
        }
    }
    return 0;
}
int dfs(int x,int a){
    if (x == t || a == 0)    return a;
    int f,flow = 0;
    for (int i = first[x]; i; i = e[i].next){
        int v = e[i].to;
        if (d[v] == d[x] + 1 && (f = dfs(v,min(a,e[i].cap - e[i].flow))) > 0){
            flow += f;
            e[i].flow += f;
            e[i ^ 1].flow -= f;
            a -= f;
            if (a == 0)    break;
        }
    }
    return flow;
}
int maxflow(){
    int flow = 0;
    while (bfs())    flow += dfs(s,INF);
    return flow;    
}
bool judge(int x,int y){
    return    (b[x][y] && (b[x - 1][y] || b[x][y - 1] || b[x + 1][y] || b[x][y + 1]) );
}
void work(int x,int y){
    int p = si[x][y];
    if ((x + y) & 1){    
        if     (b[x - 1][y])    add(p,si[x - 1][y],1),add(si[x - 1][y],p,0);
        if     (b[x + 1][y])    add(p,si[x + 1][y],1),add(si[x + 1][y],p,0);
        if     (b[x][y - 1])    add(p,si[x][y - 1],1),add(si[x][y - 1],p,0);
        if     (b[x][y + 1])    add(p,si[x][y + 1],1),add(si[x][y + 1],p,0);
        add(1,p,1),add(p,1,0);
    }    
    else     add(p,temp,1),add(temp,p,0);
}
int main(){
    int x,y;
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)    b[i][j] = 1;
    for (int i = 1; i <= k; i++)    scanf("%d%d",&x,&y),b[x][y] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)    
            if (judge(i,j))    si[i][j] = ++temp;
            temp++;    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)    
            if (si[i][j])    work(i,j);    
            s = 1,t = temp;
    printf("%d",maxflow());        
}//建图用了好久好久QwQ
by 30896 八月 21, 2016, 8:14 p.m.

Solution_ID:20392            都是渣,看我的

                   时间复杂度:Θ() 空间复杂度:Θ()

  • #include<iostream>

    #include<cstdio>

    using namespace std;

    int map[105][105],girl[105][105][2],used[105][105];

    int n,m,k,t,ans;

    bool find(int x,int y)

    {

        int i,p[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

        for(i=0;i<4;i++)

            if(x+p[i][0]>0&&x+p[i][0]<=n&&y+p[i][1]>0&&y+p[i][1]<=m)

                if(map[x+p[i][0]][y+p[i][1]]!=1&&used[x+p[i][0]][y+p[i][1]]!=t)

                {

                    used[x+p[i][0]][y+p[i][1]]=t;

                    if(girl[x+p[i][0]][y+p[i][1]][0]==0||find(girl[x+p[i][0]][y+p[i][1]][0],girl[x+p[i][0]][y+p[i][1]][1]))

                    {

                        girl[x+p[i][0]][y+p[i][1]][0]=x;

                        girl[x+p[i][0]][y+p[i][1]][1]=y;

                        girl[x][y][0]=x+p[i][0];

                        girl[x][y][1]=y+p[i][1];

                        return true;

                    }

                }

        return false;

    }

    int main()

    {

        int i,j;

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

        scanf("%d",&k);

        for(i=1;i<=k;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            map[a][b]=1;

        }

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

            for(j=1;j<=m;j++)

            {

                if(girl[i][j][0]!=0||map[i][j]==1)

                    continue;

                t++;

                if(find(i,j))

                    ans++;

            }

        printf("%d\n",ans);

        return 0;

    }


by 41254 八月 5, 2016, 3:57 p.m.

Solution_ID:18932            染色&匈牙利

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<iostream>

#include<cstring>

#define For(i,x,y) for(int i=x;i<=y;++i)

using namespace std;

const int dx[4]={0,0,-1,1};const int dy[4]={-1,1,0,0};

bool map[105][105];int tot;

struct N{

int to,next;

} edge[100*100*4+1];int head[100*100+1];

int f[100*100+1];bool used[100*100+1];

void add(int u,int v)

{

edge[++tot].to=v;edge[tot].next=head[u];head[u]=tot;

}

bool get(int x)

{

for(int i=head[x];i;i=edge[i].next)

{

int now=edge[i].to;

if(!used[now])

{

used[now]=true;

if(f[now]==0||get(f[now]))

{

f[now]=x;return true;

}

}

}

return false;

}

int main()

{


int n,m;cin>>n>>m;

memset(map,true,sizeof(map));

int T;cin>>T;int x,y;

while(T--)

{

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

map[x][y]=false;

}

For(i,1,n)

For(j,1,m)

{

if(((i+j)%2==0)&&(map[i][j]))

For(p,0,3)

{

if((i+dx[p]>0)&&(i+dx[p]<=n)&&(j+dy[p]>0)&&(j+dy[p]<=m)&&map[i+dx[p]][j+dy[p]])

{

add((i-1)*m+j,(i+dx[p]-1)*m+j+dy[p]);

}

}

}

int ans=0;

For(i,1,n*m)

{

memset(used,0,sizeof(used));

if(get(i))ans++;

}

cout<<ans;


by 27033 六月 18, 2016, 11:58 a.m.

Solution_ID:18194            SLYZ

                   时间复杂度:Θ() 空间复杂度:Θ()

讲道理,一开始我的s->i的流量为inf,但就这样能过90分……

#include<bits/stdc++.h>

#define inf 0x7ffff

#define pd(x,y,z) (x<=y&&y<=z)

using namespace std;

int s,t,n,m,k,tot=1;

int first[20010],dis[20010],cur[20010];

int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};

queue<int>q;

bool vis[20010];

struct edge

{

int u,v,w,next;

}e[400010];

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

{

e[++tot].u=x;

e[tot].v=y;

e[tot].w=z;

e[tot].next=first[x];

first[x]=tot;

}

bool bfs()

{

memset(dis,0,sizeof(dis));

q.push(s);dis[s]=1;

while (!q.empty())

{

int k=q.front();

q.pop();

for (int i=first[k];i;i=e[i].next)

if (!dis[e[i].v]&&e[i].w)

dis[e[i].v]=dis[k]+1,q.push(e[i].v);

}

if (dis[t])

for (int i=1;i<=t;i++) cur[i]=first[i];

return dis[t];

}

int dfs(int x,int maxn)

{

if (x==t) return maxn;

int used=0;

for (int i=cur[x];i;i=e[i].next)

if (dis[e[i].v]==dis[x]+1)

{

int k=dfs(e[i].v,min(maxn,e[i].w));

used+=k;

e[i].w-=k;

e[i^1].w+=k;

if (used==maxn) return maxn;

if (e[i].w) cur[x]=i;

}

if (!used) dis[x]=0;

return used;

}

main()

{

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

int x,y;

for (int i=1;i<=k;i++)

scanf("%d%d",&x,&y),

vis[(x-1)*m+y]=1;

s=n*m+1;t=n*m+2; 

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

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

if (!vis[(i-1)*m+j])

if ((i+j)&1)

{

add(s,m*(i-1)+j,1);

add(m*(i-1)+j,s,0);

for (int p=0;p<4;p++)

if (pd(1,i+dx[p],n)&&pd(1,j+dy[p],m)&&!vis[m*(i+dx[p]-1)+j+dy[p]])

add((i-1)*m+j,m*(i+dx[p]-1)+j+dy[p],1),

add(m*(i+dx[p]-1)+j+dy[p],(i-1)*m+j,0);

}

else add(m*(i-1)+j,t,1),add(t,m*(i-1)+j,0);

int ans=0;

while (bfs())

ans+=dfs(s,inf);

printf("%d",ans);

}


by 17637 四月 27, 2016, 4:46 p.m.

Solution_ID:18077            注意

                   时间复杂度:Θ() 空间复杂度:Θ()

贪心是错误算法 能过是数据水...
加强版请上3052


by 29428 四月 20, 2016, 11:46 a.m.

Solution_ID:17003            匈牙利 二分图最大匹配

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,k,sum,zo;

int f[51][51],map[2501][2501],march[2501],flag[2501];

int cx[5]={1,-1,0,0};

int cy[5]={0,0,1,-1};

int di(int x,int y){return (x-1)*m+y;}

int dfs(int v)

{

 for(int i=1;i<=zo;i++)

 {

  if(map[v][i]&&!flag[i])

  {

  flag[i]=1;

  if(!march[i]||dfs(march[i]))

  {

  march[i]=v;

  return 1;

 }

}

 }

 return 0;

}

int main()

{

 int x,y;

 cin>>n>>m>>k;

 zo=n*m;

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

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

   f[i][j]=1;

 for(int i=1;i<=k;i++)

  {

cin>>x>>y;

f[x][y]=0;

  }

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

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

   if(f[i][j])

    for(int l=0;l<4;l++)

     if(f[i+cx[l]][j+cy[l]])

       map[di(i,j)][di(i+cx[l],j+cy[l])]=1;

 for(int i=1;i<=zo;i++)

 {

  memset(flag,0,sizeof(flag));

  if(dfs(i))sum++;

 }

 cout<<sum/2;

 return 0;

}


by 31045 三月 5, 2016, 8:01 p.m.

Solution_ID:16270            o(︶︿︶)o 唉

                   时间复杂度:Θ() 空间复杂度:Θ()

我来吐槽一下这个题,我交了一个错误的匈牙利算法的程序上去,结果AC了,直到我做其他二分图匹配的题的时候才发现是错的,搞的我检查了好久,真是无语啊


by 25656 二月 2, 2016, 11:38 a.m.

Solution_ID:15155            染色,二分图匹配,匈牙利算法

                   时间复杂度:Θ(你猜:)) 空间复杂度:Θ(你一定知道,你就是不说:))

染色,二分图匹配,匈牙利算法

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;


struct node{

int adj;

node *next;

};

const int maxn = 105;

node *g[maxn * maxn];

int match[maxn * maxn] = {0}, a[maxn * maxn], n, m, ans = 0;

bool used[maxn * maxn] = {0};


int change(int x, int y)

{

return (x - 1) * m + y;

}


bool cross(int k)

{

node *p;

p = g[k];

while (p)

{

int y = p->adj;

if (!used[y])

{

used[y] = true;

if (!match[y]|| cross(match[y]))

{

match[y] = k;

return true;

}

}

p = p->next;

}

return false;

}


void solve()

{

for (int i = 1; i <= n * m; i++)

if (a[i] == 1)

{

fill(used + 1, used + 1 + n * m, 0);

if (cross(i)) ans++;

}

printf("%d\n", ans);

}


int main()

{

int k, x, y; node *p;

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

fill (a + 1, a + 1 + n * m, 1);

for (int i = 1; i <= k; i++)

{

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

a[change(x, y)] = 0;

}

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

for (int j = 2; j <= m; j += 2)

if (a[change(i, j)]) a[change(i, j)] = 2;

for (int i = 2; i <= n; i += 2)

for (int j = 1; j <= m; j += 2)

if (a[change(i, j)]) a[change(i, j)] = 2;

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

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

if (a[change(i, j)] == 1)

{

if (i - 1 > 0&& a[change(i - 1, j)] == 2)

p = new node, p->adj = change(i - 1, j), p->next = g[change(i, j)], g[change(i, j)] = p;

if (i + 1 <= n&& a[change(i + 1, j)] == 2)

p = new node, p->adj = change(i + 1, j), p->next = g[change(i, j)], g[change(i, j)] = p;

if (j - 1 > 0&& a[change(i, j - 1)] == 2)

p = new node, p->adj = change(i, j - 1), p->next = g[change(i, j)], g[change(i, j)] = p;

if (j + 1 <= m&& a[change(i, j + 1)] == 2)

p = new node, p->adj = change(i, j + 1), p->next = g[change(i, j)], g[change(i, j)] = p;

}

solve();

return 0;

}


by 32174 十二月 8, 2015, 4:43 p.m.

Solution_ID:14815            贪心正确性欠妥

                   时间复杂度:Θ() 空间复杂度:Θ()

刚好数据都是行先放更优

交一下3052就知道问题所在了



by 1004 十一月 25, 2015, 4:41 p.m.

Solution_ID:13548            这题贪心真能过= =

                   时间复杂度:Θ() 空间复杂度:Θ()

楼下下范围注意到了就可以换顺序了,另外求大神求证贪心的正确性(我也不知道有没有)

#include<cstdio>
#include<iostream>
#include<string.h>
using namespace std;
int n,m,k,x,y,ans,a[51][51];
int main()
{
  cin>>n>>m>>k;
  for(int i=1;i<=k;i++) {
    cin>>x>>y;
    a[x][y]=1; }
for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
   if(!a[i][j]&&!a[i][j+1]&&(j+1)<=m) {
      a[i][j]=a[i][j+1]=1;
      ans++; }
   if(!a[i][j]&&!a[i+1][j]&&(i+1)<=n) {
      a[i+1][j]=a[i][j]=1;
     ans++;  }
      }
   }
 cout<<ans;
}


by 14178 十月 26, 2015, 11:22 p.m.

Solution_ID:13543            Dinic

                   时间复杂度:Θ(??) 空间复杂度:Θ(o(n^2))

            1. #include<queue>
              #include<cstdio>
              #include<cstring>
              #include<algorithm>
              using namespace std;
              #define maxn 10010
              #define maxm 60010
              #define INF 1000000007
              const int dx[4] = {0,0,-1,1};
              const int dy[4] = {1,-1,0,0};
              struct edge{
                  int r,w,nxt;
              }e[maxm<<1];
              int ce = 1,head[maxn];
              int n,m,q;
              int h[maxn],S,T;
              bool map[110][110];

            2. inline bool judge(int i,int j)
              {
                  return (i && j && i <= n && j <= m && !map[i][j]);
              }
              inline void ins(int l,int r,int w)
              {
                  ce++;e[ce].r = r;e[ce].w = w;
                  e[ce].nxt = head[l],head[l] = ce;
              }
              inline void add(int l,int r,int w)
              {ins(l,r,w),ins(r,l,0);}
              inline int p(int i,int j)
              {return (i-1)*m+j;}

            3. inline bool bfs()
              {
                  queue <int> q;
                  memset(h,-1,sizeof(h));
                  q.push(S);
                  h[S] = 0;
                  while (!q.empty())
                  {
               int x = q.front();q.pop();
               for (int i = head[x] ; i ; i = e[i].nxt)
                   if (h[e[i].r] == -1 && e[i].w)
                   {
                h[e[i].r] = h[x] + 1;
                q.push(e[i].r);
                   }
                  }
                  return h[T] != -1;
              }

            4. inline int dfs(int x,int f)
              {
                  if (x == T) return f;
                  int used = 0,w;
                  for (int i = head[x] ; i ; i = e[i].nxt)
               if (h[e[i].r] == h[x] + 1 && e[i].w)
               {
                   w = dfs(e[i].r,min(f-used,e[i].w));
                   e[i].w -= w;
                   e[i^1].w += w;
                   used += w;
                   if (used == f) return f;
               }
                  if (!used) h[x] = -1;
                  return used;
              }

            5. int dinic()
              {
                  int tmp = 0;
                  while(bfs()) tmp += dfs(S,INF);
                  return tmp;
              }

            6. void build()
              {
                  T = n * m + 1;
                  for (int i = 1 ; i <= n ; ++i)
               for (int j = 1 ; j <= m ; ++j)
                   if ((i + j & 1) && (!map[i][j]))
                   {
                add(S,p(i,j),1);
                for (int k = 0 ; k < 4 ; ++k)
                    if (judge(i+dx[k],j+dy[k]))
                 add(p(i,j),p(i+dx[k],j+dy[k]),1);
                   }else if(!(i+j&1)) add(p(i,j),T,1);
              }

            7. int main()
              {
                  scanf("%d%d%d",&n,&m,&q);
                  for (int i = 1 ; i <= q ; ++i)
                  {
               int x,y;
               scanf("%d%d",&x,&y);
               map[x][y] = 1;
                  }
                  build();
                  printf("%d\n",dinic());
              }
              这里写题解


by 15692 十月 26, 2015, 10:35 p.m.

Solution_ID:12795            吓死宝宝了。什么匈牙利,宝宝不会

                   时间复杂度:Θ() 空间复杂度:Θ()

看题解,吓死宝宝了。。。。。
什么匈牙利,什么染色(墨水???)。。。
宝宝什么都不会,只会一个贪心。。。。
还好宝宝没见过世面。。。。
不然宝宝就被你们吓死你。。。。。。。
宝宝就用贪心过了。。。。

!!!!!!!!!注意哦。。。特判顺序不能更换(不然会WA一个)!!!!!!!!!!!!


#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
bool  b[120][120];
int n,m,tot,x,y,t;
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%d",&t);
	for (int i=1;i<=t;i++)
	{
		scanf("%d%d",&x,&y);
		b[x][y]=1;
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		if (j+1<=m)
		{
			if (b[i][j]==0&&b[i][j+1]==0)
			{
				tot++;
				b[i][j]=1;
				b[i][j+1]=1;
			}
		}
		if (i+1<=n)
		{
			if (b[i][j]==0&&b[i+1][j]==0)
			{
				tot++;
				b[i][j]=1;
				b[i+1][j]=1;
			}
		}
	}
	cout<<tot;
}

by 13849 十月 15, 2015, 9:57 a.m.

Solution_ID:12641            第一次染色 简直快死了

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstring>

#include<queue>

#include<vector>

#include<cstdio>

#define maxn 100000

#define inf 999999999

using namespace std;

int a[200][200];

bool color[200][200],used[200][200];

struct edge{

int to,cap,rev;

};

vector<edge>G[maxn];

void addedge(int from,int to,int cap){

G[from].push_back((edge){to,cap,G[to].size()});

G[to].push_back((edge){from,0,G[from].size()-1});

}


int level[maxn],ltr[maxn];

void BFS(int s){

queue<int>que;

que.push(s);

memset(level,-1,sizeof(level));

level[s]=0;

while(!que.empty()){

int k=que.front();

que.pop();

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

edge &e=G[k][i];

if(level[e.to]==-1&&e.cap>0){

level[e.to]=level[k]+1;

que.push(e.to);

}

}

}

return;

}

int DFS(int s,int t,int flow){

if(s==t)

return flow;

for(int &i=ltr[s];i<G[s].size();i++){

edge &e=G[s][i];

if(level[e.to]>level[s]&&e.cap>0){

int d=DFS(e.to,t,min(e.cap,flow));

if(d>0){

e.cap-=d;

G[e.to][e.rev].cap+=d;

return d;

}

}

}

return 0;

}

int max_flow(int s,int t){

int flow=0;

BFS(s);

while(level[t]>0){

memset(ltr,0,sizeof(ltr));

int f=DFS(s,t,inf);

while(f>0){

flow += f;

f=DFS(s,t,inf);

}

BFS(s);

}

return flow;

}

int main(){

     int m,n;

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

     int t=1;

     for(int i=0;i<m;i++)

     {

      bool temp=i%2;

     for(int j=0;j<n;j++){

      color[i][j]=temp;

      a[i][j]=t++;

      temp=!temp;

     }}

     int q;

     cin>>q;

     for(int i=0;i<q;i++){

      int d,e;

      cin>>d>>e;

      used[d-1][e-1]=1;

     }

     int s=50000;

t=50001;

     for(int i=0;i<m;i++)

     for(int j=0;j<n;j++){

      int id=a[i][j];

      if(color[i][j]&&!used[i][j]){

      addedge(s,id,1);

      if(i!=0&&!used[i-1][j]){

      addedge(id,a[i-1][j],1);

      }

      if(i!=n-1&&!used[i+1][j]){

      addedge(id,a[i+1][j],1);

      }

      if(j!=0&&!used[i][j-1]){

      addedge(id,a[i][j-1],1);

      }

      if(j!=n-1&&!used[i][j+1]){

      addedge(id,a[i][j+1],1);

      }

      }

      else if(!used[i][j]){

      addedge(id,t,1);

      }

     }

     cout<<max_flow(s,t);


}


by 17480 十月 12, 2015, 10:11 a.m.