【题解】Inspection UVa 1440 LA 4597 NEERC 2009

题目传送门：https://vjudge.net/problem/UVA-1440

看上去很像DAG的最小路径覆盖QwQ？

反正我是写了一个上下界网络流，建模方法清晰易懂。

建立源$s$，向每个原图中的点连边，下界为$0$，上界为$\infty$，表示在每个点可以放置无限多的人。

建立汇$t$，每个原图中的点向汇连边，下界为$0$，上界为$\infty$，表示人可以在任意一个点停止滑雪。

对于原图中的每条弧$<u,v>$，连边$<u,v>$，下界为$1$，上界为$\infty$，表示这条路至少要被检查一遍。

然后跑一个有源汇上下界最小流就好啦OvO。

不会求上下界网络流的看这里：http://www.cnblogs.com/mlystdcall/p/6734852.html

输出方案？瞎搞QwQ。任选一个“需要放置人的点”开始dfs，在每个点的出边中任选一个“还需要被访问的”继续dfs，详见代码和注释。

这样输出方案为什么是对的？时间太久远辣我已经忘辣QwQ。

代码如下：

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 namespace ISAP {

     const int MAXV = MAXN;

     const int MAXE = ( MAXV*MAXV/ + MAXV* )*;

     struct Edge {

         int u, v, c, f;

         Edge(){}

         Edge( int u, int v, int c, int f ):

             u(u),v(v),c(c),f(f){}

     }edge[MAXE<<];

     int n, m, s, t, ss, tt;

     int head[MAXV], nxt[MAXE<<], eid[MAXE<<], eidx;

     void init( int n2, int ss2, int tt2 ) { // 初始化，设置附加源和附加汇

         n = n2; ss = ss2; tt = tt2;

         m = eidx = ;

         memset( head, -, sizeof(head) );

     }

     int adde( int u, int v, int c ) { // 添加一条只有上界的边

         int rtn = m;

         eid[eidx] = m; nxt[eidx] = head[u]; head[u] = eidx++;

         edge[m++] = Edge(u,v,c,);

         eid[eidx] = m; nxt[eidx] = head[v]; head[v] = eidx++;

         edge[m++] = Edge(v,u,,);

         return rtn;

     }

     int adde2( int u, int v, int b, int c ) { // 添加一条有上下界的边，返回边的下标

         int rtn = adde(u,v,c-b);

         adde(ss,v,b);

         adde(u,tt,b);

         return rtn;

     }

     // 以下ISAP板子

     int prev[MAXV], dist[MAXV], num[MAXV], cur[MAXV], res[MAXV];

     queue<int> bfsq;

     void bfs() {

         for( int i = ; i <= n; ++i ) dist[i] = n;

         dist[t] = ; bfsq.push(t);

         while( !bfsq.empty() ) {

             int u = bfsq.front(); bfsq.pop();

             for( int i = head[u]; ~i; i = nxt[i] ) {

                 Edge &e = edge[eid[i]];

                 if( dist[e.v] == n ) {

                     dist[e.v] = dist[u] + ;

                     bfsq.push(e.v);

                 }

             }

         }

     }

     void augment() {

         int u = t, flow = res[t];

         while( u != s ) {

             int i = prev[u];

             edge[i].f += flow;

             edge[i^].f -= flow;

             u = edge[i].u;

         }

     }

     bool advance( int &u ) {

         for( int i = cur[u]; ~i; i = nxt[i] ) {

             Edge &e = edge[eid[i]];

             if( e.c > e.f && dist[e.v] +  == dist[u] ) {

                 prev[e.v] = cur[u] = i;

                 res[e.v] = min( res[u], e.c - e.f );

                 u = e.v;

                 return true;

             }

         }

         return false;

     }

     bool retreat( int &u ) {

         if( --num[dist[u]] ==  ) return false;

         int newd = n;

         for( int i = head[u]; ~i; i = nxt[i] ) {

             Edge &e = edge[eid[i]];

             if( e.c > e.f ) newd = min( newd, dist[e.v] +  );

         }

         ++num[ dist[u] = newd ];

         cur[u] = head[u];

         if( u != s ) u = edge[prev[u]].u;

         return true;

     }

     int solve( int s2, int t2 ) { // 以s2为源，t2为汇跑最大流

         s = s2; t = t2;

         bfs();

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

             cur[i] = head[i], ++num[dist[i]];

         int u = s, flow = ;

         res[s] = INF;

         while( dist[s] < n ) {

             if( u == t ) {

                 augment();

                 flow += res[t];

                 u = s;

             }

             if( !advance(u) )

                 if( !retreat(u) )

                     break;

         }

         return flow;

     }

 }

 int n, s, t, ss, tt; // 点的个数，源，汇，附加源，附加汇

 namespace Solve {

     using ISAP::head;

     using ISAP::nxt;

     using ISAP::eid;

     using ISAP::Edge;

     using ISAP::edge;

     bool first;

     void dfs( int u ) { // dfs输出方案

         // printf( "Debug: u = %d\n", u );

         if( !first ) putchar(' ');

         first = false;

         printf( "%d", u );

         for( int i = head[u]; ~i; i = nxt[i] ) {

             Edge &e = edge[eid[i]];

             if( e.v <= n && e.f >  ) { // 任选一条边走下去

                 // printf( "going eid = %d, from %d to %d, flow_left = %d\n", eid[i], e.u, e.v, e.f );

                 --e.f;

                 dfs(e.v);

                 return;

             }

         }

     }

     void addbound() { // 把每条边流量加上下界，恢复成原图的样子，方便输出方案

         using ISAP::m;

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

             Edge &e = edge[eid[i]];

             if( e.u <= n && e.v <= n && e.c >  )

                 ++e.f;

         }

     }

 }

 namespace Debug { // 调试用QwQ

     void print_flow() {

         using ISAP::edge;

         using ISAP::Edge;

         using ISAP::eid;

         using ISAP::m;

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

             Edge &e = edge[eid[i]];

             if( e.u <= n && e.v <= n && e.c >  )

                 printf( "eid = %d, from %d to %d, flow = %d\n", eid[i], e.u, e.v, e.f );

         }

     }

     void print_flow2() {

         using ISAP::edge;

         using ISAP::Edge;

         using ISAP::eid;

         using ISAP::m;

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

             Edge &e = edge[eid[i]];

             if( e.f >  )

                 printf( "eid = %d, from %d to %d, flow = %d\n", eid[i], e.u, e.v, e.f );

         }

     }

 }

 int main() {

     while( scanf( "%d", &n ) ==  ) {

         s = n+, t = n+, ss = n+, tt = n+;

         ISAP::init(tt,ss,tt);

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

             int mi; scanf( "%d", &mi );

             while( mi-- ) {

                 int v; scanf( "%d", &v );

                 ISAP::adde2(i,v,,INF);

             }

             ISAP::adde2(s,i,,INF);

             ISAP::adde2(i,t,,INF);

         }

         int flow1 = ISAP::solve(ss,tt);

         // printf( "flow1 = %d\n", flow1 );

         // Debug::print_flow();

         // Debug::print_flow2();

         int tsedge = ISAP::adde2(t,s,,INF); // 存储弧<t,s>的信息，调试用QwQ

         int ans = ISAP::solve(ss,tt);

         // printf( "t_s flow = %d\n", ISAP::edge[tsedge].f );

         // Debug::print_flow();

         // Debug::print_flow2();

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

         Solve::addbound(); // 把每条图中的边流量加上下界，恢复成原图的样子，方便输出方案

         while( ans ) {

             using namespace Solve;

             for( int i = head[s]; ~i; i = nxt[i] ) {

                 Edge &e = edge[eid[i]];

                 if( e.v <= n && e.f >  ) { // 任选一个点dfs，输出方案

                     first = true;

                     --e.f;

                     --ans;

                     dfs(e.v);

                         putchar('\n');

                 }

             }

         }

     }

     return ;

 }

巴特西

【题解】Inspection UVa 1440 LA 4597 NEERC 2009

最新文章

热门文章