TOJ---1023---最小路径覆盖---

这应该算今天噢不对都可以算昨天做的最有质量的一题了至于什么是最小路径覆盖之类的 = 今天下午再说吧有点累了

明天又要上高数了上学期期末高数卷必跪的节奏。。。。

作妹啊。。。。。。。。

先给出链接要是你也喜欢熬夜今晚A了它吧

touch me

------------------- 以下可以看成我的碎碎念

碎觉了

全世界失眠多好

你如果失眠了应该感到开心起码有人可以让你失眠

好久不曾失眠

今天看到一句话

陪伴是最深情的告白

-----------------------以上全与本文无关

嗯。。应该怎么讲呢？发现我所写下的内容还是只有我自己能看懂作妹。。。。。

最小路径覆盖它也是二分图匹配中一个重要的概念的

我们对于它的求解是将它从有向图 -> 无向图

你可能会很奇怪这怎么发生呢?

很简单我们取有向图中的一个点 A 你应该清楚每个顶点都有一个入度和出度的概念我们可以看成A' A''

然后将它分成2个集合来看这样就很像我们以前接触的二分图了吧左右 2个集合

可能我们都知道最小路径覆盖 = 顶点个数 - 二分图最大匹配

那这个等式为什么会成立呢？

我们想得到的最小的路径条数那么是不是得寻找一个边数最多的匹配方式使尽量多的顶点连在一条路上那么余下的顶点就各自为一条路径

这里你需要注意的是一个顶点自身即可以成为一条路径

可能我这边讲的太简单了点要是配个图肯定理解起来更好可是我太 lazy 了

记得对于它是我和晓爷在离散课上圈圈画画讨论出来的

你也可以去参考一下大牛博客对它的理解

我这里放上我的代码

 1 // 极小路径覆盖 = N - 最大覆盖数
 2 // x1 y1 x2 y2  （ x1 , y1 ) , ( x2 , y2 )
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdio>
 6 using namespace std;
 7 
 8 const int size = 520;
 9 struct data
10 {
11     int time;
12     int x1 , y1 , x2 , y2;
13 }car[size];
14 bool vis[size];
15 int linker[size];
16 bool mp[size][size];
17 int n;
18 
19 int abs( int x )
20 {
21     return x>0?x:-x;
22 }
23 
24 bool judge( data p , data q )
25 {
26     return p.time + abs(p.x2-p.x1) + abs(p.y2-p.y1) + abs(p.x2-q.x1) + abs(p.y2-q.y1 ) < q.time; //判断i j 是否可以相连
27 }
28 
29 bool match( int u )
30 {
31     for( int v = 0 ; v<n ; v++ )
32     {
33         if( !vis[v] && mp[u][v] )
34         {
35             vis[v] = true;
36             if( linker[v]==-1 || match( linker[v] ) )
37             {
38                 linker[v] = u;
39                 return true;
40             }
41         }
42     }
43     return false;
44 }
45 
46 int getSum()
47 {
48     int cnt = 0;
49     memset( linker , -1 , sizeof(linker) );
50     for( int u = 0 ; u<n ; u++ )
51     {
52         memset( vis , false , sizeof(vis) );
53         if( match(u) )
54             cnt++;
55     }
56     return cnt;
57 }
58 
59 int main()
60 {
61     int t;
62     int i , j;
63     int h , m;
64     while( ~scanf("%d",&t) )
65     {
66         while( t-- )
67         {
68             memset( mp , false , sizeof(mp) );
69             scanf( "%d",&n );
70             for( i = 0 ; i<n ; i++ )
71             {
72                 scanf( "%d:%d %d %d %d %d",&h,&m,&car[i].x1,&car[i].y1,&car[i].x2,&car[i].y2 );
73                 car[i].time = 60*h + m;
74             }
75             for( i = 0 ; i<n ; i++ )  // 要是 可以在上一个地点结束后 来到下一地点 就可以看成 i j有边 可以连接起来
76             {
77                 for( j = i+1 ; j<n ; j++ )
78                 {
79                     if( judge( car[i] , car[j] ) )
80                     {
81                         mp[i][j] = true;
82                     }
83                 }
84             }
85             printf( "%d
",n-getSum() );
86         }
87     }
88     return 0;
89 }

View Code

端午来了

学期要结束了

学妹们快要来了

离结束单身还远吗

just follow your heart