A.A + B problem(待填坑)
B.Cat VS Dog(二分图匹配)
喜欢cat和喜欢dog的人构成了二分图，如果两个人有冲突则连一条边，则问题转化为二分图最大点独立集问题。ans=n-最大匹配。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... struct Child{string like, dis;}cat[N], dog[N];
int G[N][N], link[N], used[N], cat_num, dog_num; int dfs(int k)
{
FO(i,,dog_num) if(!used[i] && G[k][i]) {
used[i]=;
if(link[i]==- || dfs(link[i])) {link[i]=k; return ;}
}
return ;
}
int maxMatch()
{
int cnt=;
FO(i,,cat_num) {
mem(used,);
if(dfs(i)) ++cnt;
}
return cnt;
}
int main()
{
int n, m, p;
string a, b;
while(cin>>n>>m>>p) {
mem(G,); mem(link,-);
cat_num=dog_num=;
while(p--) {
cin>>a>>b;
if(a[] == 'C') cat[cat_num].like=a, cat[cat_num].dis=b, cat_num++;
else dog[dog_num].like=a, dog[dog_num].dis=b, dog_num++;
}
FO(i,,cat_num) FO(j,,dog_num) if(cat[i].like==dog[j].dis || cat[i].dis==dog[j].like) G[i][j]=;
cout<<cat_num+dog_num-maxMatch()<<endl;
}
return ;
}
C.Checkers(二分+LCA+辗转相除法)
考虑点对(a,b,c)可以转换的点对。容易发现这其实是一个无限二叉树。
如果左边的棋子或者右边的棋子往中间跳，就对应着父亲边往上的过程。中间的棋子往左跳，对应着左孩子边。中间的往右跳，对应着右孩子边。
那么我们判断解的存在性就相当于找到他们是不是同一个根。判断最小的解就相当于在树上找到LCA。
可以通过辗转相除法来优化向上爬的操作。由于不能倍增找LCA，我们二分向上爬的深度验证即可。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... LL a[], b[], root[], dep[], dis[], temp1[], temp2[]; void get_root(LL x)
{
root[x]=(x?b[]:a[]); dep[x]=;
LL val1, val2, t;
if (x) val1=b[]-b[], val2=b[]-b[];
else val1=a[]-a[], val2=a[]-a[];
while (val1!=val2) {
if (val1<val2) {
if (val2%val1) t=val2/val1;
else t=val2/val1-;
root[x]+=t*val1; dep[x]+=t; val2-=t*val1;
}
else {
if (val1%val2) t=val1/val2;
else t=val1/val2-;
root[x]-=t*val2; dep[x]+=t; val1-=t*val2;
}
}
dis[x]=val1;
}
void go_up(LL (&a)[], LL dep)
{
while (dep) {
LL val1=a[]-a[], val2=a[]-a[], t;
if (val1>val2) {
if (val1%val2) t=val1/val2;
else t=val1/val2-;
if (dep>=t) a[]-=t*val2, a[]-=t*val2, dep-=t;
else a[]-=dep*val2, a[]-=dep*val2, dep=;
}
else {
if (val2%val1) t=val2/val1;
else t=val2/val1-;
if (dep>=t) a[]+=t*val1, a[]+=t*val1, dep-=t;
else a[]+=dep*val1, a[]+=dep*val1, dep=;
}
}
}
int main ()
{
while (~scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a[],&a[],&a[],&b[],&b[],&b[])) {
sort(a,a+); sort(b,b+);
get_root(); get_root();
if (root[]!=root[] || dis[]!=dis[]) {puts("NO"); continue;}
LL ans=;
if (dep[]>dep[]) {
LL t=dep[]-dep[]; dep[]=dep[];
go_up(a,t);
ans+=t;
}
else if (dep[]<dep[]) {
LL t=dep[]-dep[]; dep[]=dep[];
go_up(b,t);
ans+=t;
}
if (a[]==b[]&&a[]==b[]&&a[]==b[]) {printf("YES\n%I64d\n",ans); continue;}
LL l=, r=dep[]+, mid;
while (l<r) {
mid=(l+r)>>;
temp1[]=a[]; temp1[]=a[]; temp1[]=a[];
temp2[]=b[]; temp2[]=b[]; temp2[]=b[];
go_up(temp1,mid); go_up(temp2,mid);
if (temp1[]==temp2[]&&temp1[]==temp2[]&&temp1[]==temp2[]) r=mid;
else l=mid+;
}
printf("YES\n%I64d\n",ans+*r);
}
return ;
}
D.DICS(DP)
这是字符串编辑距离的拓展，多了一个改变后缀操作。dp数组多开一维记录改变的后缀类型。直接记搜即可。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int dp[N][N][], len1, len2;
char s1[N], s2[N]; int dfs(int x, int y, int z)
{
if (~dp[x][y][z]) return dp[x][y][z];
if (x==len1&&y==len2) return ;
if (x==len1) return len2-y;
if (y==len2) return len1-x;
int ans=min(dfs(x,y+,z)+,dfs(x+,y,z)+);
if (z==) ans=min(ans,dfs(x+,y+,z)+(s1[x]!=s2[y]));
else ans=min(ans,dfs(x+,y+,z)+(z!=s2[y]));
if ((z==&&s1[x]!=s2[y]) || (z&&z!=s2[y])) ans=min(ans,dfs(x+,y+,s2[y])+);
return dp[x][y][z]=ans;
}
int main ()
{
while () {
scanf("%s",s1);
if (s1[]=='#') break;
scanf("%s",s2);
len1=strlen(s1); len2=strlen(s2);
FO(i,,len1) {
if (s1[i]<='z'&&s1[i]>='a') s1[i]=s1[i]-'a'+;
else s1[i]=s1[i]-'A'+;
}
FO(i,,len2) {
if (s2[i]<='z'&&s2[i]>='a') s2[i]=s2[i]-'a'+;
else s2[i]=s2[i]-'A'+;
}
mem(dp,-);
printf("%d\n",dfs(,,));
}
return ;
}
E.Earth Hour(水题)
先抽象成图，然后问题转化为求图中3个点的生成树的最短路。数据范围很小，直接从这3个点bfs一次。因为这连接3个点的生成树一定是从图中一个点出发可以直接到达的。
枚举这个点更新答案即可。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... struct Edge{int p, next;}edge[N*N];
struct Cir{int x, y, r;}cir[N];
int head[N], cnt, fa[N], vis[N]; queue<int>Q;
int find(int x)
{
int s, temp;
for (s=x; fa[s]>=; s=fa[s]) ;
while (s!=x) temp=fa[x], fa[x]=s, x=temp;
return s;
}
void union_set(int x, int y)
{
int temp=fa[x]+fa[y];
if (fa[x]>fa[y]) fa[x]=y, fa[y]=temp;
else fa[y]=x, fa[x]=temp;
}
void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}
void init(){cnt=; mem(head,); mem(fa,-);}
int dis(int x, int y){return (cir[x].x-cir[y].x)*(cir[x].x-cir[y].x)+(cir[x].y-cir[y].y)*(cir[x].y-cir[y].y);}
int main ()
{
int T, n, u, v, w;
scanf("%d",&T);
while (T--) {
int ans=;
init();
scanf("%d",&n);
FOR(i,,n) scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r);
FOR(i,,n) FOR(j,i+,n) if (dis(i,j)<=(cir[i].r+cir[j].r)*(cir[i].r+cir[j].r)) {
add_edge(i,j), add_edge(j,i);
u=find(i), v=find(j);
if (u!=v) union_set(u,v);
}
u=find(); v=find(); w=find();
if (u!=v||u!=w||v!=w) {puts("-1"); continue;}
FOR(i,,n) {
mem(vis,-); vis[i]=;
while (!Q.empty()) Q.pop();
Q.push(i);
while (!Q.empty()) {
int w=Q.front(); Q.pop();
for (int v=head[w]; v; v=edge[v].next) {
int u=edge[v].p;
if (vis[u]!=-) continue;
vis[u]=vis[w]+; Q.push(u);
}
}
if (vis[]!=-&&vis[]!=-&&vis[]!=-) ans=max(ans,n--vis[]-vis[]-vis[]);
}
printf("%d\n",ans);
}
}
F.YY's new problem(线段树维护字符串hash)
问题转化为 2*a[j]=a[i]+a[k].对于每一个a[j], 只需要验证点对(a[i],a[k])是否出现在a[j]的两侧。复杂度是O(n^2).
如果发现对于a[j],点对是连续的,比如(a[j]-1,a[j]+1),(a[j]-2,a[j]+2),(a[j]-k,a[j]+k).
从前往后扫描数组，如果扫描到a[m],就将vis[a[m]]置1，扫描到a[j]时，只需要验证每个点对的vis值是否是相等的。这样复杂度还是O(n^2).
实际上点对的分布在数轴上是关于点a[j]对称的，那么我们只需要检查关于vis值字符串a[j]-k...a[j]-2,a[j]-1和字符串a[j]+k...a[j]+2,a[j]+1.是否相等就行了。
于是我们需要一个能够快速实现更新一个点的hash，查询一个区间的hash值的数据结构，hash由于具有区间合并性。我们可以用线段树来维护区间的hash值。
复杂度是O(nlogn).
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int a[N];
LL seg1[N<<], seg2[N<<], _hash[N]; LL mult_mod(LL a, LL b, LL c)
{
a%=c; b%=c;
LL ret=, tmp=a;
while (b) {
if (b&) {
ret+=tmp;
if (ret>c) ret-=c;
}
tmp<<=;
if (tmp>c) tmp-=c;
b>>=;
}
return ret;
}
LL pow_mod(LL a, LL n, LL mod)
{
LL ret=, temp=a%mod;
while (n) {
if (n&) ret=mult_mod(ret,temp,mod);
temp=mult_mod(temp,temp,mod);
n>>=;
}
return ret;
}
void init(int p, int l, int r)
{
if (l<r) {
int mid=(l+r)>>;
init(lch); init(rch);
seg1[p]=(seg1[p<<]*_hash[(r-l+)>>]+seg1[p<<|])%MOD;
seg2[p]=(seg2[p<<|]*_hash[(r-l+)>>]+seg2[p<<])%MOD;
return ;
}
seg1[p]=seg2[p]=;
}
void insert(int p, int l, int r, int L)
{
if (L>r||L<l) return ;
if (L==l&&L==r) seg1[p]=seg2[p]=;
else {
int mid=(l+r)>>;
insert(lch,L); insert(rch,L);
seg1[p]=(seg1[p<<]*_hash[(r-l+)>>]+seg1[p<<|])%MOD;
seg2[p]=(seg2[p<<|]*_hash[(r-l+)>>]+seg2[p<<])%MOD;
}
}
LL query1(int p, int l, int r, int L, int R)
{
if (L>r||R<l) return ;
if (L<=l&&R>=r) return seg1[p]*_hash[R-r]%MOD;
int mid=(l+r)>>;
return (query1(lch,L,R)+query1(rch,L,R))%MOD;
}
LL query2(int p, int l, int r, int L, int R)
{
if (L>r||R<l) return ;
if (L<=l&&R>=r) return seg2[p]*_hash[l-L]%MOD;
int mid=(l+r)>>;
return (query2(lch,L,R)+query2(rch,L,R))%MOD;
}
int main ()
{
int n, T, flag;
_hash[]=;
FOR(i,,) _hash[i]=_hash[i-]*%MOD;
scanf("%d",&T);
while (T--) {
flag=;
scanf("%d",&n);
FOR(i,,n) scanf("%d",a+i);
init(,,n);
FOR(i,,n) {
if (a[i]!= && a[i]!=n) {
int t=min(n-a[i],a[i]-);
//printf("%d %lld %lld\n",i,query1(1,1,n,a[i]-t,a[i]-1),query2(1,1,n,a[i]+1,a[i]+t));
if (query1(,,n,a[i]-t,a[i]-)!=query2(,,n,a[i]+,a[i]+t)) {flag=; break;}
}
insert(,,n,a[i]);
}
puts(flag?"Y":"N");
}
return ;
}
G.Where am I(计算几何)
把小圆缩成点，大圆缩小，可以发现路径只会形成一个三角形，计算出这个三角形即可。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
const double eps = 1e-;
const double pi = acos(-1.0);
typedef struct
{
double x,y;
}TPoint;
typedef struct
{
double x,y,r;
}TCircle;
TCircle ball,sball;
TPoint vec,convert;
double T;
int flag;
inline double squ(double x)
{
return x*x;
}
double dot(TPoint a,TPoint b,TPoint c)
{
return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
}
int cross(TPoint a,TPoint b,TPoint c)
{
double ret = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if(ret>eps)
return ;
return -;
}
void work()
{
convert.x = ball.x;
convert.y = ball.y;
sball.x -= convert.x;
sball.y -= convert.y;
ball.x =;
ball.y = ;
ball.r -= sball.r;
TPoint me = {sball.x,sball.y};
if(fabs(vec.x) < eps && fabs(vec.y) < eps)
{/*vec is zero*/
me.x += convert.x;
me.y += convert.y;
printf("%.1f %.1f\n",me.x,me.y);
return;
}
if(fabs(ball.r)<eps)
{/*sball.r == ball.r*/
me.x += convert.x;
me.y += convert.y;
printf("%.1f %.1f\n",me.x,me.y);
return;
}
if(squ(me.x+T*vec.x)+squ(me.y+T*vec.y)+eps<squ(ball.r))
{
me.x = me.x+T*vec.x;
me.y = me.y+T*vec.y;
me.x += convert.x;
me.y += convert.y;
printf("%.1f %.1f\n",me.x,me.y);
return ;
}
double k=vec.y/vec.x;
double b=me.y-k*me.x;
double x1;
//printf("k:%f b:%f %f\n",k,b,ball.r);
if(vec.x<)
{
x1=(-k*b-sqrt(squ(k*ball.r)+squ(ball.r)-squ(b)))/(squ(k)+);
}
else
{
x1=(-k*b+sqrt(squ(k*ball.r)+squ(ball.r)-squ(b)))/(squ(k)+1.0);
}
/*fjjjjj*/
double y1=k*x1+b;
/**
** x1 && y1
**/
// printf("(x1,y1)%f %f\n",x1,y1);
TPoint tmp1 = {x1,y1};
TPoint tmp2 = {,};
double u = dot(tmp1,tmp2,me);
flag = cross(tmp1,tmp2,me);
/**
flag
**/
//printf("flag:%d\n",flag);
u = u/(sqrt(squ(x1-me.x)+squ(y1-me.y))*ball.r);
double l=(u)*ball.r;
l *= ;
u = acos(u);
/**
l
**/
//printf("l:%f\n",l);
double t1 = l/sqrt(squ(vec.x)+squ(vec.y));
__int64 time = (T-(x1-me.x)/vec.x)/t1;
/**
time
**/
//printf("time:%I64d\n",time);
T = T-(x1-me.x)/vec.x-time*t1;
/**
lefttime
**/
// printf("lefttime:%f\n",T);
/*上面以对 很可能是角度算错了 下面的要仔细验证下!!!*/
double u2=atan2(y1,x1);
double u3 = (time+)*(pi-*u)*flag;
u2 += time*(pi-*u)*flag;
double x2 = ball.r*cos(u2);
double y2 = ball.r*sin(u2);
//printf("%f %f(x2,y2)\n",x2,y2);
TPoint vec2;
vec2.x = vec.x*cos(u3)-vec.y*sin(u3);
vec2.y = vec.x*sin(u3)+vec.y*cos(u3);
me.x = x2+vec2.x*T+convert.x;
me.y = y2+vec2.y*T+convert.y;
printf("%.1f %.1f\n",me.x,me.y);
return;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("G.in","r",stdin);
freopen("G.out","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf",&ball.x,&ball.y,&ball.r);
scanf("%lf%lf%lf",&sball.x,&sball.y,&sball.r);
scanf("%lf%lf%lf",&vec.x,&vec.y,&T);
work();
}
return ;
}
H.R(N)(水题)
打出平方表二分搜一下即可。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int a[N], P; bool bin_sea(int x)
{
int l=, r=P+, mid;
while (l<r) {
mid=(l+r)>>;
if (l==mid) break;
if (a[mid]>x) r=mid;
else l=mid;
}
return a[l]==x;
}
int main ()
{
int n;
P=(int)sqrt(1e9+0.5);
FOR(i,,P) a[i]=i*i;
while (~scanf("%d",&n)) {
if (n==) {puts(""); continue;}
LL ans=;
if (bin_sea(n)) ans+=;
FOR(i,,n) {
if (*i*i>n) break;
else if (*i*i==n) ans+=;
else if (bin_sea(n-i*i)) ans+=;
}
printf("%lld\n",ans);
}
return ;
}
I.Equivalent Sets(强连通分量)
易知道当且仅当一个图是强连通图时题意成立。先把题中给出的图强连通分量缩点，然后变成了一个DAG，问题转化为求DAG最少加几条边变成强连通图。
有结论max(源，汇)。(具体还不会证)
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... struct Edge{int p, next;}edge[N<<];
int head[N], cnt;
int Low[N], DFN[N], Stack[N], Belong[N], num[N];
int Index, top, scc, a[N<<][], chu[N], ru[N];
bool Instack[N]; void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}
void Tarjan(int u)
{
int v;
Low[u]=DFN[u]=++Index; Stack[top++]=u; Instack[u]=true;
for (int i=head[u]; i; i=edge[i].next) {
v=edge[i].p;
if (!DFN[v]) {
Tarjan(v);
if (Low[u]>Low[v]) Low[u]=Low[v];
}
else if (Instack[v]&&Low[u]>DFN[v]) Low[u]=DFN[v];
}
if (Low[u]==DFN[u]) {
scc++;
do{
v=Stack[--top]; Instack[v]=false;
Belong[v]=scc; num[scc]++;
}while (v!=u);
}
}
void solve(int n)
{
mem(DFN,); mem(Instack,); mem(num,);
Index=scc=top=;
FOR(i,,n) if (!DFN[i]) Tarjan(i);
}
void init(){mem(head,); mem(chu,); mem(ru,); cnt=;}
int main ()
{
int n, m, u, v;
while (~scanf("%d%d",&n,&m)) {
init();
FOR(i,,m) scanf("%d%d",&u,&v), add_edge(u,v), a[i][]=u, a[i][]=v;
solve(n);
if (scc==) {puts(""); continue;}
FOR(i,,m) {
if (Belong[a[i][]]==Belong[a[i][]]) continue;
++chu[Belong[a[i][]]]; ++ru[Belong[a[i][]]];
}
int ans1=, ans2=;
FOR(i,,scc) {
if (chu[i]==) ans1++;
if (ru[i]==) ans2++;
}
printf("%d\n",max(ans1,ans2));
}
return ;
}