hiho一下 第140周-清理海報(DAG+dfs)

記錄一個菜逼的成長。。

題目連結

官方題解

題解裡面貌似有錯

這裡應該還有條3->4的邊

有人會問為什麼會有2->4這條邊，從圖上看2的四個點都被覆寫了。

這就是建圖時要注意的地方了，建圖時我們隻要根據兩個矩形是否相交建圖就可以了，不必去管矩形的四個點是否被覆寫。

因為雖然2的四個點都被覆寫，但是2是作為1和4之間的關聯的。撕1時，會先撕去2，然後再撕去4.是以這裡要有條2->4的邊。這樣在搜尋時就不會漏了。

然後枚舉第一次要撕去的海報，這裡判斷一下矩形的四個點是否被覆寫。

隻要有一個點未被覆寫就可以直接去搜尋了。

PS：這裡我用y1數組不知道為什麼會CE..說定義重了。然而程式裡隻定義了一次。。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))
const int maxn =  + ;
int x1[maxn],y11[maxn],x2[maxn],y2[maxn];
int f[maxn][],vis[maxn];
vector<int>g[maxn];
int w,h,n;
bool overlap(int i, int j)
{
    return !(x1[i] >= x2[j] || x1[j] >= x2[i] || y11[i] >= y2[j] || y11[j] >= y2[i]);
}
bool check(int i,int x,int y)
{
    return x >= x1[i] && x <= x2[i] && y >= y11[i] && y <= y2[i];
}
int dfs(int x)
{
    int ans = ;
    for( int i = ; i < g[x].size(); i++ ){
        if(!vis[g[x][i]]){
            vis[g[x][i]] = ;
            ans += dfs(g[x][i]);
        }
    }
    return ans + ;
}
int main()
{
    while(~scanf("%d%d%d",&w,&h,&n)){
        for( int i = ; i <= n; i++ ){
            scanf("%d%d%d%d",&x1[i],&y11[i],&x2[i],&y2[i]);
        }
        for( int i = ; i <= n; i++ ){
            for( int j = i+; j <= n; j++ ){
                if(check(j,x1[i],y11[i]))f[i][] = ;
                if(check(j,x1[i],y2[i]))f[i][] = ;
                if(check(j,x2[i],y2[i]))f[i][] = ;
                if(check(j,x2[i],y11[i]))f[i][] = ;
            }
        }
        for( int i = ; i <= n; i++ ){
            for( int j = ; j < i; j++ ){
                if(overlap(i,j))g[j].pb(i);
            }
        }
        int  mx = -;
        int id;
        for( int i = ; i <= n; i++ ){
            if(f[i][] && f[i][] && f[i][] && f[i][])continue;
            cl(vis,);
            int ret = dfs(i);
            if(ret > mx){
                mx = ret;
                id = i;
            }
        }
        printf("%d %d\n",mx,id);
    }
    return ;
}