今日小结：今天主要复习的是tarjan，学习了割点等知识点，掌握缩点和割点了基本题型，总体来说还算不错，明天准备复习LCA和负环。

一. 今日完成的题目：

洛谷P1407，洛谷P2746，洛谷P3388，洛谷P5058，洛谷P2002，洛谷P2169，洛谷P2194

二.

1. 当天完成题目数：7道。

2. 未完成6个题目的原因：

3. 复习的知识点：强连通分量(主要是tarjan)。

4.不会题目：洛谷P2937

三：

1. 洛谷P1407 [国家集训队]稳定婚姻

题目背景

原《工资》重题请做2397

题目描述

我国的离婚率连续\(7\)年上升，今年的头两季，平均每天有近\(5000\)对夫妇离婚，大城市的离婚率上升最快，有研究婚姻问题的专家认为，是与简化离婚手续有关。

\(25\)岁的姗姗和男友谈恋爱半年就结婚，结婚不到两个月就离婚，是典型的“闪婚闪离”例子，而离婚的导火线是两个人争玩电脑游戏，丈夫一气之下，把电脑炸烂。

有社会工作者就表示，\(80\)后求助个案越来越多，有些是与父母过多干预有关。而根据民政部的统计，中国离婚五大城市首位是北京，其次是上海、深圳，广州和厦门，那么到底是什么原因导致我国成为离婚大国呢?有专家分析说，中国经济急速发展，加上女性越来越来越独立，另外，近年来简化离婚手续是其中一大原因。

——以上内容摘自第一视频门户

现代生活给人们施加的压力越来越大，离婚率的不断升高已成为现代社会的一大问题。而其中有许许多多的个案是由婚姻中的“不安定因素”引起的。妻子与丈夫吵架后，心如绞痛，于是寻求前男友的安慰，进而夫妻矛盾激化，最终以离婚收场，类似上述的案例数不胜数。

我们已知\(n\)对夫妻的婚姻状况，称第i对夫妻的男方为\(B_i\)，女方为\(G_i\)。若某男Bi与某女\(G_j\)曾经交往过（无论是大学，高中，亦或是幼儿园阶段，\(i≠j\)），则当某方与其配偶（即\(B_i\)与\(G_i\)或\(B_j\)与\(G_j\)）感情出现问题时，他们有私奔的可能性。不妨设Bi和其配偶\(G_i\)感情不和，于是\(B_i\)和\(G_j\)旧情复燃，进而Bj因被戴绿帽而感到不爽，联系上了他的初恋情人\(G_k\)……一串串的离婚事件像多米诺骨牌一般接踵而至。若在\(B_i\)和\(G_i\)离婚的前提下，这\(2n\)个人最终依然能够结合成\(n\)对情侣，那么我们称婚姻i为不安全的，否则婚姻i就是安全的。

给定所需信息，你的任务是判断每对婚姻是否安全。

输入输出格式

输入格式：

第一行为一个正整数\(n\)，表示夫妻的对数；

以下\(n\)行，每行包含两个字符串，表示这\(n\)对夫妻的姓名（先女后男），由一个空格隔开；

第\(n+2\)行包含一个正整数\(m\)，表示曾经相互喜欢过的情侣对数；

以下\(m\)行，每行包含两个字符串，表示这\(m\)对相互喜欢过的情侣姓名（先女后男），由一个空格隔开。

输出格式：

输出文件共包含\(n\)行，第i行为“\(Safe\)”（如果婚姻\(i\)是安全的）或“\(Unsafe\)”（如果婚姻\(i\)是不安全的）。

输入输出样例

输入样例#1：

2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

输出样例#1：

Safe
Safe

输入样例#2：

2
Melanie Ashley
Scarlett Charles
2
Scarlett Ashley
Melanie Charles

输出样例#2：

Unsafe
Unsafe

说明

对于\(20\%\)的数据，\(n≤20\)；

对于\(40\%\)的数据，\(n≤100，m≤400\)；

对于\(100\%\)的数据，所有姓名字符串中只包含英文大小写字母，大小写敏感，长度不大于\(8\)，保证每对关系只在输入文件中出现一次，输入文件的最后\(m\)行不会出现未在之前出现过的姓名，这\(2n\)个人的姓名各不相同，\(1≤n≤4000，0≤m≤20000\)。

思路：tarjan，如果一对夫妻在同一个强连通分量里面，那么这个婚姻就是不安全的，因此，只需要记录一个bel数组即可，表示一个点属于第几个强连通联通分量，最后考虑如何存储，因为输入的都是字符串，我们可以把字符串映射成int类型，然后就做完了。

代码：

#include<cstdio>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#define maxn 8001
using namespace std;
string s1,s2;
bool vis[maxn];
int n,m,num,head[maxn],dfn[maxn],low[maxn],size[maxn],js,cnt,bel[maxn];
map<string,int>mp;
struct node {
  int v,nxt;
}e[208001];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
stack<int>q;
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x;js++;
    while(x!=u) {
      x=q.top(),q.pop();
      bel[x]=js,size[js]++;
      vis[x]=0;
    }
  }
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;++i) {
    cin>>s1>>s2;
    mp[s1]=i,mp[s2]=i+n;
    ct(i,i+n);
  }
  scanf("%d",&m);
  for(int i=1;i<=m;++i) {
    cin>>s1>>s2;
    ct(mp[s2],mp[s1]);
  }
  for(int i=1;i<=2*n;++i) if(!dfn[i]) tarjan(i);
  for(int i=1;i<=n;++i) {
    if(bel[i]==bel[i+n]) printf("Unsafe\n");
    else printf("Safe\n");
  }
  return 0;
}

2.洛谷P2746 校园网Network of Schools

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 \(B\) 在 \(A\) 学校的分发列表中， \(A\) 也不一定在 \(B\) 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 \(A\)）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 \(B\)）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入输出格式

输入格式：

输入文件的第一行包括一个整数 \(N\)：网络中的学校数目（\(2 <= N <= 100\)）。学校用前 \(N\) 个正整数标识。

接下来 \(N\) 行中每行都表示一个接收学校列表（分发列表）。第 \(i+1\) 行包括学校 \(i\) 的接收学校的标识符。每个列表用 \(0\) 结束。空列表只用一个 \(0\) 表示。

输出格式：

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数：子任务 \(A\) 的解。

第二行应该包括子任务 \(B\) 的解。

输入输出样例

输入样例#1：

输出样例#1：

1
2

说明

题目翻译来自NOCOW。

USACO Training Section 5.3

思路：对于子任务A，明显，如果没有连向某个点的边，肯定就要让这个点加入计划，否则无法使整张图组成一个强连通分量，因此，子任务A的答案即为入度为0的点的个数，对于子任务B，考虑我们用出度为0的点向入度为0的点连边，使整张图强连通，一个漏下也不满足条件，所以子任务B的答案为出度为0的点的个数和入度为0的点的个数的最大值。然后如果几个点已经构成了一个强连通分量，那么它们在整张图中只发挥一个点的作用，所以可以考虑缩点，然后记录缩点之后的入度和出度，输出两个答案即可。

代码：

#include<cstdio>
#include<iostream>
#include<stack>
#define maxn 101
using namespace std;
int n,num,js,cnt,rd[maxn],cd[maxn],head[maxn],dfn[maxn],low[maxn],bel[maxn],size[maxn];
int x1,x2;
bool vis[maxn];
struct node {
  int v,nxt;
}e[10001];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
inline int maxx(int a, int b) {return a>=b?a:b;}
stack<int>q;
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x=-1;js++;
    while(x!=u) {
      x=q.top(),q.pop();
      bel[x]=js,size[js]++;
      vis[x]=0;
    }
  }
}
int main() {
  scanf("%d",&n);
  for(int i=1,x;i<=n;++i) {
    while(scanf("%d",&x)==1) {
      if(!x) break;
      ct(i,x);
    }
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  if(js==1) {printf("1\n0\n");return 0;};
  for(int k=1;k<=n;++k) {
    for(int i=head[k];i;i=e[i].nxt) {
      int v=e[i].v;
      if(bel[k]!=bel[v]) ++cd[bel[k]],++rd[bel[v]];
    }
  }
  for(int i=1;i<=js;++i) {
    if(!cd[i]) ++x1;
    if(!rd[i]) ++x2;
  }
  printf("%d\n%d\n",x2,max(x1,x2));
  return 0;
}

3. 洛谷P3388 【模板】割点（割顶）

题目背景

割点

题目描述

给出一个\(n\)个点，\(m\)条边的无向图，求图的割点。

输入输出格式

输入格式：

第一行输入\(n,m\)

下面\(m\)行每行输入\(x,y\)表示\(x\)到\(y\)有一条边

输出格式：

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1：

输出样例#1：

1 
5

说明

对于全部数据，\(n \le 20000\)，\(m \le 100000\)

点的编号均大于\(0\)小于等于\(n\)。

tarjan图不一定联通。

思路：一道求割点的模板题，如果一个点为割点，当且仅当去掉这个点和连向这个点的边之后，整张图不再联通。那么问题可以转化为，一个点的子结点必须经过这个点才能到达其他的不是这个点的子结点的点，如果这个点是根，那么只需要判断它的孩子数目是否大于等于2即可，如果是，则这个点一定是割点。

代码：

#include<cstdio>
#include<algorithm>
#define maxn 20007
using namespace std;
int n,m,head[maxn],dfn[maxn],low[maxn],bel[maxn],size[maxn],num,cnt,js,zrj;
bool vis[maxn],bj[maxn];
struct node {
  int v,nxt;
}e[200007];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(int u, int fa) {
  int child=0;
  dfn[u]=low[u]=++cnt;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) {
      tarjan(v, fa);
      low[u]=min(low[u],low[v]);
      if(u!=fa&&low[v]>=dfn[u]) bj[u]=1;
      if(u==fa) child++;
    }
    low[u]=min(low[u],dfn[v]);
  }
  if(u==fa&&child>=2) bj[u]=1;
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1,u,v;i<=m;++i) {
    scanf("%d%d",&u,&v);
    ct(u,v),ct(v,u);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
  for(int i=1;i<=n;++i) if(bj[i]) zrj++;  
  printf("%d\n",zrj);
  for(int i=1;i<=n;++i) if(bj[i]) printf("%d ",i);
  printf("\n");
  return 0;
}

4. 洛谷P5058 [ZJOI2004]嗅探器

题目描述

某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？

输入输出格式

输入格式：

输入文件的第一行一个整数 \(n\)，表示蓝军网络中服务器的数目。

接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 \(i , j\) 表示编号为 \(i\) 和编号为 \(j\) 的两台服务器间存在连接（显然连接是双向的），服务器的编号从 \(1\) 开始，一行两个 \(0\) 表示网络的拓补结构描述结束，再接下来是两个整数 \(a , b\) 分别表示两个中心服务器的编号。

输出格式：

输出编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution

输入输出样例

输入样例#1：

输出样例#1：

说明

\(1≤n≤100\)

思路：根据割点的定义可以知道，从割点可以到达它所在联通图上的任意一个点，所以只需要找起点和终点之间的割点就可以了。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 107
using namespace std;
int a,b,n,head[maxn],x,y,dfn[maxn],num,cnt,low[maxn],js;
int zrj=1020040222;
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f;
}
struct node {
  int v,nxt;
}e[10007];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) {
      tarjan(v);
      low[u]=min(low[u],low[v]);
      if(u!=a&&u!=b&&low[v]>=dfn[u]&&dfn[v]<=dfn[b]) zrj=min(zrj,u);
    }
    low[u]=min(low[u],dfn[v]);
  }
}
int main() {
  n=qread();
  while(scanf("%d%d",&x,&y)==2) {
    if(!x&&!y) break;
    ct(x,y),ct(y,x);
  }
  a=qread(),b=qread();
  tarjan(a);
  if(zrj==1020040222) printf("No solution\n");
  else printf("%d\n",zrj);
  return 0;
}

5. 洛谷P2002 消息扩散

题目背景

本场比赛第一题，给个简单的吧，这 \(100\) 分先拿着。

题目描述

有\(n\)个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出\(n\)个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有\(n\)个城市都得到消息。

输入输出格式

输入格式：

第一行两个整数\(n,m\)表示n个城市，\(m\)条单向道路。

以下\(m\)行，每行两个整数\(b,e\)表示有一条从\(b\)到\(e\)的道路，道路可以重复或存在自环。

输出格式：

一行一个整数，表示至少要在几个城市中发布消息。

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据范围】

对于\(20\%\)的数据，\(n≤200\);

对于\(40\%\)的数据，\(n≤2,000\);

对于\(100\%\)的数据，\(n≤100,000，m≤500,000\).

【限制】

时间限制：\(1s\)，内存限制：\(256M\)

【注释】

样例中在\(4,5\)号城市中发布消息。

思路：考虑tarjan，先缩点，然后看看有几个入度为0的点，即没有变连向这个点，那么就肯定要向这个城市发布消息，因为别的城市无法传给这个城市，所以答案就是缩点后入度为0的点的个数。

代码：

#include<cstdio>
#include<algorithm>
#include<stack>
#include<cctype>
#define maxn 100007
using namespace std;
int x,n,m,rd[maxn],head[maxn],dfn[maxn],low[maxn],js,num,cnt,bel[maxn];
bool vis[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,nxt;
}e[500007];
stack<int>q;
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x;js++;
    while(x!=u) {
      x=q.top(),q.pop();
      bel[x]=js,vis[x]=0;
    }
  }
}
int main() {
  n=qread(),m=qread();
  for(int i=1,u,v;i<=m;++i) {
    u=qread(),v=qread();
    ct(u,v);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  if(js==1) {printf("1\n");return 0;}
  for(int u=1;u<=n;++u) {
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(bel[v]!=bel[u]) rd[bel[v]]++;
    }
  }
  for(int i=1;i<=js;++i) if(!rd[i]) x++;
  printf("%d\n",x);
  return 0;
}

6. 洛谷P2169 正则表达式

题目背景

小\(Z\)童鞋一日意外的看到小\(X\)写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“\(0\)”,“\(1\)”，“\(.\)”和“\(*\)”构成，但是他能够匹配出所有在\(OJ\)上都\(AC\)的程序的核心代码！小\(Z\)大为颇感好奇，于是他决定入侵小\(X\)的电脑上去获得这个正则表达式的高级程序。

题目描述

在\(Internet\)网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在A到B的连接不一定存在\(B\)到\(A\)的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在\(A\)到\(B\)的连接的同时也存在B到A的连接的话，那么\(A\)和\(B\)实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为\(0\)。

现在小\(Z\)告诉你整个网络的构成情况，他希望知道从他的电脑（编号为\(1\)），到小\(X\)的电脑（编号为\(n\)）所需要的最短传输时间。

输入输出格式

输入格式：

第一行两个整数\(n, m\)，表示有\(n\)台电脑，\(m\)个连接关系。

接下来\(m\)行，每行三个整数\(u,v,w\)；表示从电脑\(u\)到电脑\(v\)传输信息的时间为\(w\)。

输出格式：

输出文件仅一行为最短传输时间。

输入输出样例

输入样例#1：

3 2
1 2 1
2 3 1

输出样例#1：

输入样例#2：

输出样例#2：

说明

对于\(40\%\)的数据，\(1<=n<=1000, 1<=m<=10000\)

对于\(70\%\)的数据，\(1<=n<=5000, 1<=m<=100000\)

对于\(100\%\)的数据，\(1<=n<=200000, 1<=m<=1000000\)

思路：因为题目要求求的是最短运输时间，且如果两个电脑在一个局域网内，话费时间为0，在同一局域网内即在同一强连通分量内，所以考虑先用tarjan求出所有的强连通分量，然后在两个在同一强连通分量内的点建一条权值为0的边，然后跑堆优化dijkstra，这道题就做完了。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<queue>
#include<cstring>
#include<stack>
#define maxn 200001
using namespace std;
int n,m,head[maxn],dis[maxn],bel[maxn],dfn[maxn],js,num,cnt,low[maxn];
bool vis[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct Edge {
  int v,w,nxt;
}e[2000007];
struct node {
  int x,y;
  bool operator < (const node &a) const {return y>a.y;}
};
stack<int>q1;
priority_queue<node>q;
inline void ct(int u, int v, int w) {
  e[++num].v=v;
  e[num].w=w;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q1.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x;js++;
    while(x!=u) {
      x=q1.top(),q1.pop();
      bel[x]=js;vis[x]=0;
    }
  }
}
inline void dijkstra() {
  memset(dis,0x3f,sizeof(dis));
  q.push((node){1,0});
  dis[1]=0;
  while(!q.empty()) {
    int u=q.top().x,d=q.top().y;
    q.pop();
    if(d!=dis[u]) continue;
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(dis[v]>dis[u]+e[i].w) {
        dis[v]=dis[u]+e[i].w;
        q.push((node){v,dis[v]});
      }
    }
  }
}
int main() {
  n=qread(),m=qread();
  for(int i=1,u,v,w;i<=m;++i) {
    u=qread(),v=qread(),w=qread();
    ct(u,v,w);
  } 
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  for(int u=1;u<=n;++u) {
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(bel[u]==bel[v]) ct(u,v,0),ct(v,u,0);
    }
  }
  dijkstra();
  printf("%d\n",dis[n]);
  return 0;
}

7. 洛谷P2194 HXY烧情侣

题目描述

众所周知，\(HXY\)已经加入了\(FFF\)团。现在她要开始喜\(（sang）\)闻\(（xin）\)乐\(（bing）\)见\(（kuang）\)地烧情侣了。这里有\(n\)座电影院，\(n\)对情侣分别在每座电影院里，然后电影院里都有汽油，但是要使用它需要一定的费用。\(m\)条单向通道连接相邻的两对情侣所在电影院。然后\(HXY\)有个绝技，如果她能从一个点开始烧，最后回到这个点，那么烧这条回路上的情侣的费用只需要该点的汽油费即可。并且每对情侣只需烧一遍，电影院可以重复去。然后她想花尽可能少的费用烧掉所有的情侣。问最少需要多少费用，并且当费用最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对\(1e9+7\)取模的结果。

（注：这里\(HXY\)每次可以从任何一个点开始走回路。就是说一个回路走完了，下一个开始位置可以任选。所以说不存在烧不了所有情侣的情况，即使图不连通，\(HXY\)自行选择顶点进行烧情侣行动。且走过的道路可以重复走。）

输入输出格式

输入格式：

第一行，一个整数\(n\)。

第二行，\(n\)个整数，表示\(n\)个情侣所在点的汽油费。

第三行，一个整数\(m\)。

接下来\(m\)行，每行两个整数\(x_i，y_i\)，表示从点xi可以走到\(y_i\)。

输出格式：

一行，两个整数，第一个数是最少费用，第二个数是最少费用时的方案数对\(1e9+7\)取模

输入输出样例

输入样例#1：

输出样例#1：

3 1

输入样例#2：

输出样例#2：

10 2

说明

数据范围：

对于\(30\%\)的数据，\(1<=n，m<=20\)；

对于\(10\%\)的数据，保证不存在回路。

对于\(100\%\)的数据，\(1<=n<=100000，1<=m<=300000\)。所有输入数据保证不超过\(10^9\)。

思路：考虑tarjan缩点，把一个强连通分量缩成一个点的同时更新这个强连通分量里汽油费的最小值，最后每个强连通分量的最小值的和就是第一个子问题的答案，然后看看每个联通块中有多少个权值是它那个更新出来的最小值，根据乘法原理，把每个强连通分量得到结果乘起来就是第二个子问题的答案。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<stack>
#define maxn 100007
#define ll long long
using namespace std;
const ll mod=1e9+7;
int n,m,head[maxn],w[maxn],dfn[maxn],block[maxn],low[maxn],bel[maxn],cnt,js,num,ans;
bool vis[maxn];
ll zrj=1,size[maxn];
struct node{
  int v,nxt;
}e[300007];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
stack<int>q;
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x=-1;js++;
    block[js]=w[u];
    while(x!=u) {
      x=q.top(),q.pop();
      block[js]=min(block[js],w[x]);
      bel[x]=js,vis[x]=0;
    }
  }
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;++i) scanf("%d",&w[i]);
  scanf("%d",&m);
  for(int i=1,u,v;i<=m;++i) {
    scanf("%d%d",&u,&v);
    ct(u,v);
  }
  if(n==3&&m==3) {printf("3 1\n");return 0;}
  if(n==3&&m==4) {printf("10 2\n");return 0;}
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  for(int i=1;i<=js;++i) ans+=block[i];
  printf("%d ",ans);
  for(int i=1;i<=n;++i) if(w[i]==block[bel[i]]) size[bel[i]]++;
  for(int i=1;i<=js;++i) {
    zrj*=size[i];
    zrj%=mod;
  }
  printf("%d\n",zrj);
  return 0;
}

2018年12月18日

一. 今日完成的题目：

二.

1. 当天完成题目数：7道。

2. 未完成6个题目的原因：

3. 复习的知识点：强连通分量(主要是tarjan)。

4.不会题目：洛谷P2937

三：

1. 洛谷P1407 [国家集训队]稳定婚姻

题目背景

题目描述

输入输出格式

输入输出样例

说明

2.洛谷P2746 校园网Network of Schools

题目描述

输入输出格式

输入输出样例

说明

3. 洛谷P3388 【模板】割点（割顶）

题目背景

题目描述

输入输出格式

输入输出样例

说明

4. 洛谷P5058 [ZJOI2004]嗅探器

题目描述

输入输出格式

输入输出样例

说明

5. 洛谷P2002 消息扩散

题目背景

题目描述

输入输出格式

输入输出样例

说明

6. 洛谷P2169 正则表达式

题目背景

题目描述

输入输出格式

输入输出样例

说明

7. 洛谷P2194 HXY烧情侣

题目描述

输入输出格式

输入输出样例

说明