Starry

最大流问题，FF算法： 链式前向星建边，异或来求反向边。 const int N=2e3+86; struct edge{int to,nxt,w;}e[N*2];int hd[N],tot=1; void add(int u,int v,int w){ e[++tot]=(edge){v,hd[u],w}; hd[u]=tot; } int n,m,x; bitset<286> vis; int dfs(int p,int flow){ if(p

struct edge{int to,nxt,w;}e[N*2];int hd[N],tot=1; void add(int u,int v,int w){ e[++tot]=(edge){v,hd[u],w}; hd[u]=tot; }

第一问应该转化为求入度为0的点个数 第二问取入度为0的点个数与出度为0的点个数的较大值，注意特判仅有一个强连通分量的情况。 参考：题解 P2746 【[USACO5.3]校园网Network of Schools】 首先用Kosaraju求出各个强连通分量缩点，然后求出各个强连通分量间的有向边。 ```cpp const int N = 186; int n, cnt,mark[N],c,r; vi v[N], rv[N], dfn, scc[N]; set s[N], rs[N]; bitset<200> vis; void dfs(int

在计算科学中，Kosaraju的算法（又称为–Sharir Kosaraju算法）是一个线性时间(linear time)算法找到的有向图的强连通分量。它利用了一个事实，逆图（与各边方向相同的图形反转, transpose graph）有相同的强连通分量的原始图。 首先第一遍dfs扫一遍得到逆后序压倒栈dfn中 int vis[MAX]; vector<int> dfn; f(i, 1, n){ if (!vis[i]) dfs(i); } void dfs(int x) { vis[x] &

缩点，将该有向有环图变为有向无环图，然后dp求解 因为已经变为有向无环图，所以其中为号强连通分量的儿子 首先用Kosaraju找强连通分量，第一遍dfs遍历，并从后往前压入dfn栈中，然后再FILO进行第二遍dfs，对于每次遍历到的点均构成一个强连通分量。 然后用set容器储存各个强连通分量的边，用dp求解 const int N = 2e4; int n, m, a[N], mark[N], t[N]; vi rim[N], nrim[N], dfn; bitset<10086> vis; set<int> s[N]; LL dp[N]; void d