題意：
? ? ? 給你一個DAG,然后問你最少多少條路徑能覆蓋所有需要覆蓋的點。


思路：
? ? ? 最小路徑覆蓋，太明顯了，每個點向它右下方的點連邊，然后...沒啥難的地方，不說了。


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


#define N_node 24 * 24 + 10
#define N_edge 24 * 24 * 24 * 24 + 100


typedef struct
{
? ? int x ,y;
}NODE;


typedef struct
{
? ? int to ,next;
}STAR;


NODE node[N_node];
STAR E[N_edge];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[N_node];


void add(int a ,int b)
{
? ? E[++tot].to = b;
? ? E[tot].next = list[a];
? ? list[a] = tot;
}


int DFS_XYL(int x)
{
? ? for(int k = list[x] ;k ;k = E[k].next)
? ? {
? ? ? ? int to = E[k].to;
? ? ? ? if(mkdfs[to]) continue;
? ? ? ? mkdfs[to] = 1;
? ? ? ? if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))
? ? ? ? {
? ? ? ? ? ? mkgx[to] = x;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? }
? ? return 0;
}




int main ()
{
? ? int a ,b ,i ,j, nowt ,n;
? ? while(~scanf("%d %d" ,&a ,&b) && a != -1)
? ? {
? ? ? ? nowt = 1;
? ? ? ? node[nowt].x = a;
? ? ? ? node[nowt].y = b;
? ? ? ? while(scanf("%d %d" ,&a ,&b) && a && b)
? ? ? ? {
? ? ? ? ? ? node[++nowt].x = a;
? ? ? ? ? ? node[nowt].y = b;
? ? ? ? }
? ? ? ? n = nowt;
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? {
? ? ? ? ? ? if(i == j) continue;
? ? ? ? ? ? if(node[i].x <= node[j].x && node[i].y <= node[j].y)
? ? ? ? ? ? add(i ,j);
? ? ? ? }
? ? ? ? memset(mkgx ,255 ,sizeof(mkgx));
? ? ? ? int Ans = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? memset(mkdfs ,0 ,sizeof(mkdfs));
? ? ? ? ? ? Ans += DFS_XYL(i);
? ? ? ? }
? ? ? ? printf("%d\n" ,n - Ans);
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ1548最小路径覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。