P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]

摘要:
牛贝西是美味草的鉴赏家。她想去尽可能多的草原品尝青草。贝西总是从草地1出发,最后回到草地1。她想通过尽可能多的草原。贝西在通通的一片草地上只吃一次草,所以一片草地可以经过很多次。因为草原由单行道连接,这给贝西的品尝工作带来了极大的不便。贝西想偷偷后退一次,但最多只能后退一次。输入格式Input:第一行输入包含NandM,给出字段数和单向路径数。以下M行各描述一条路径。每条线包含两个不同的字段编号X和Y,对应于从X到Y的路径。同样的道路永远不会出现。输入:第一行:草地的数量n,道路的数量m。下面的m行,每行x和y,表示从x到y有一条单行线,不会有重复的道路。

题目描述

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ's paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

约翰有n块草场,编号1到n,这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家,她想到达尽可能多的草场去品尝牧草。

贝西总是从1号草场出发,最后回到1号草场。她想经过尽可能多的草场,贝西在通一个草场只吃一次草,所以一个草场可以经过多次。因为草场是单行道连接,这给贝西的品鉴工作带来了很大的不便,贝西想偷偷逆向行走一次,但最多只能有一次逆行。问,贝西最多能吃到多少个草场的牧草。

输入格式

INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

输入:

第一行:草场数n,道路数m。

以下m行,每行x和y表明有x到y的单向边,不会有重复的道路出现。

输出格式

OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

输出:

一个数,逆行一次最多可以走几个草场。

输入输出样例

输入 #1
7 10 
1 2 
3 1 
2 5 
2 4 
3 7 
3 5 
3 6 
6 5 
7 2 
4 7 

输出 #1
6 

说明/提示

SOLUTION NOTES:

Here is an ASCII drawing of the sample input:

v---3-->6
7   |  |
^  v  |
|  1   |
|   |   v
|   v   5
4<--2---^

Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling

backwards on the path between 5 and 3. When she arrives at 3 she

cannot reach 6 without following another backwards path.

思路

  P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]第1张

    相当坎坷的一道紫题,数据也不算水了, 前前后后大概想了两个小时, 写了一个小时, wa了一个小时.

  首先, 知道这题是求最长路;

  其次, 注意到反向只能走一次这个问题, 怎么做到只能反向走一次.

  先把点分成三种情况来讨论一下,

  1 直接可以由 1 号草坪走来的;

  2 可以走到 1 号草坪的;

  3 和 1 号点完全没有任何关系的.

  显然这道题根本不会用到第 3 这种情况, 所以只需要建立一个正图和一个反向图, 在DAG上跑最长路, 显然可以由 1 号节点做起点在拓扑序上跑dp就可以了.

  最后枚举每条反边, ans 就是 反向走到此条反边的正向图的父亲边的距离 + 正向走到此条反边的距离 - 1 号节点所在的连通块大小( 就是这里wa穿了, 因为有数据是1号节点直接在一个连通块里的 ), 并维护 ans 的最大值即可.

CODE

P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]第2张P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]第3张
  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 1e5 + 7;
  7 
  8 int head[maxn], dfn[maxn], low[maxn], st[maxn];
  9 int cnt = 0, tot = 0, tim = 0, top = 1, n, m, cl = 0, ans = 0;
 10 int vis[maxn];
 11 int color[maxn];
 12 int sz[maxn];
 13 int dis[maxn][5];
 14 int head1[maxn << 1][5], cnt1, edge1[maxn << 1][5], nxt1[maxn << 1][5];
 15 int in[maxn << 1][5];
 16 
 17 /*
 18 head[],结构体edge:存边
 19 
 20 dfn[],low[]:tarjan中数组
 21 
 22 st[]:模拟栈
 23 
 24 out[]:出边
 25 
 26 sd[]:强连通分量存储
 27 
 28 dq[]:统计答案
 29 */
 30 
 31 template<class T>inline void read(T &res)
 32 {
 33     char c;T flag=1;
 34     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 35     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 36 }
 37 
 38 struct Edge{
 39     int nxt, to;
 40 }edge[maxn * 2];
 41 
 42 inline void BuildGraph(int from, int to)
 43 {
 44     cnt++;
 45     edge[cnt].to = to;
 46     edge[cnt].nxt = head[from];
 47     head[from] = cnt;
 48 }
 49 
 50 void tarjan(int x)
 51 {
 52     tim++;
 53     dfn[x] = low[x] = tim;
 54     st[top] = x;
 55     top++;
 56     vis[x] = 1;
 57     for(int i = head[x] ; i != 0; i = edge[i].nxt)
 58     {
 59         int u = edge[i].to;
 60         if(vis[u] == 0)
 61         {
 62             tarjan(u);
 63             low[x]=min(low[x],low[u]);
 64         }
 65         else if(vis[u] == 1)
 66                 low[x]=min(low[x],dfn[u]);
 67     }
 68     if(dfn[x] == low[x])
 69     {
 70         cl++;
 71         do
 72         {
 73             top--;
 74             color[st[top]] = cl;
 75             vis[st[top]] = -1;
 76             sz[color[st[top]]]++;
 77         }while( st[top] != x );
 78     }
 79     return ;
 80 }
 81 
 82 void addedge(int u, int v, int cas) {
 83     if(cas == 1) {
 84         cnt++;
 85     }
 86     in[v][cas]++;
 87     edge1[cnt][cas] = v;
 88     nxt1[cnt][cas] = head1[u][cas];
 89     head1[u][cas] = cnt;
 90 }
 91 
 92 void topo(int cas) {
 93     dis[color[1]][cas] = sz[color[1]];
 94     queue<int> q;
 95     for ( int i = 1; i <= cl; ++i ) {
 96         if(in[i][cas] == 0) {
 97             q.push(i);
 98         }
 99     }
100     while(!q.empty()) {
101         int u = q.front();
102         q.pop();
103         for ( int i = head1[u][cas]; i; i = nxt1[i][cas] ) {
104             int v = edge1[i][cas];
105             dis[v][cas] = max(dis[v][cas], dis[u][cas] + sz[v]);
106             if(--in[v][cas] == 0) {
107                 q.push(v);
108             }
109         }
110     }
111 }
112 
113 int main()
114 {
115     scanf("%d %d",&n, &m);
116     for ( int i = 1; i <= m; ++i ) {
117        int x, y;
118        scanf("%d %d",&x, &y);
119        BuildGraph(x, y);
120     }
121     for ( int i = 1; i <= n; ++i ) {
122         if( !vis[i] ) {
123             tarjan(i);
124         }
125     }
126     cnt = 0;
127     for ( int i = 1; i <= n; ++i ) {
128         for ( int j = head[i]; j; j = edge[j].nxt ) {
129             int v = edge[j].to;
130             if(color[i] != color[v]) {
131                 addedge(color[i], color[v], 1);
132                 addedge(color[v], color[i], 2);
133             }
134         }
135     }
136     memset(dis, 0xef, sizeof(dis));
137     ans = sz[color[1]];
138     topo(1), topo(2);
139     for ( int i = 1; i <= n; ++i ) {
140         for ( int j = head[i]; j; j = edge[j].nxt ) {
141             int v = edge[j].to;
142             if(color[i] != color[v]) {
143                 ans = max(ans, dis[color[v]][1] + dis[color[i]][2] - sz[color[1]]);
144             }
145         }
146     }
147     cout << ans << endl;
148     return 0;
149 }
View Code

免责声明:文章转载自《P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【高速接口-RapidIO】5、Xilinx RapidIO核例子工程源码分析Mysql运维管理-Mysql增量备份及分库分表备份数据恢复实战12下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

您的硬件设置已被更改,请重新启动计算机,使更改生效

在Win7旗舰系统上,出现“您的硬件设置已更改,请重新启动计算机以使更改生效”。开机后将弹出“您的硬件设置已更改,请重新启动计算机”窗口。不要关闭它。打开任务管理器,右键单击以转到进程,查看其中是否有正在运行的进程。进程名称为:atieclxx.exe右键单击进程打开文件的位置。将此程序移出原始文件夹(最好是另一个磁盘),然后重新启动计算机。...

ubuntu 常见安装软件错误

安装xlibs dev.2。错误:apt-get-installlibqt3-headers libqt3-mt-dev3。错误:这基本上意味着它要安装许多KDEspecificpackagestowork。这个'configure:aapt-get-installbuild essential7。错误:...

C#基础系列过滤器与特性

过滤器和特性结合在一起,在方法上优雅地使用过滤器。3.在过滤器中,。NETFrameWork提供了两种类型:一种是提供给ASP的筛选器。NETMVC在命名空间下使用System.Web。另一个是提供给ASP的过滤器。NETWebApi在命名空间下使用System.Web.Http.Filters。这两种类型不能混合使用,否则无法拦截并生效。...

选包

安装系统后,将不会安装一些基本工具。此时,您可以根据yum的要求安装它们。你也可以使用任何你想要的时尚。...

Windows怎么从命令行下载文件

具体步骤如下:1.打开cmd。exeWin+R或git的bush接口。2.启动powershell。2.在命令行中输入startpowershell以启动powershell。3.下载操作。1.在powershell中输入$client=newobjectSystem.Net.WebClient3.2。exe文件,然后输入$client。下载文件('X','...

文件(夹)对比利器WinMerge

IDE中自带的svn功能较弱,还好有winMerge弥补了它的缺陷,它可以对比文件、文件夹,使用起来还是较为方便,界面也是中文。“开始”菜单,弹出对话框中选择需要进行对比的文件夹或文件然后选择一个过滤器,它自带就可以过滤掉svn目录,如需要过滤其它一些指定的目录,则需要自己修改过滤器的规则了,也很简单。...