今晚
题目内容:
给定一张 \(n\) 个点 \(m\) 条边的有向图 \(G\) 。
有 \(n\) 个硬币。初始时有的正面朝上，有的反面朝上。每次你可以手动翻转一枚。
如果在 \(G\) 中有边 \(a\rightarrow b\) ，那么当第 \(a\) 枚硬币（被手动或自动）翻转后，第 \(b\) 枚也会被自动翻转。注意：它可以传递下去。
但如果你手动翻转某一枚后会触发无限次操作，那波特就直接炸了，你不能使其触发这种情况。
给定初始每个硬币的状态，求至少操作多少次后能使所有硬币都正面朝上。
无解输出 -1 。
输入格式:
n m
x_1,x_2,x_3,...,x_n (表示每枚硬币的状态，1表示正面朝上，0表示反面朝上)
a_1 b_1 (表示一条有向边a_1->b_1，下同)
a_2 b_1
a_3 b_3
......
a_n b_n
输出格式:
一行一个整数，表示答案。
样例1:
putin:
5 10
0 0 0 0 0
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
putout:
3
样例2:
putin:
3 3
0 0 0
1 2
2 3
3 1
putout:
-1
提示:
对于 \(30\%\) 的数据，\(n,m\leq 10\) 。
对于 \(50\%\) 的数据，\(n,m\leq 3000\) 。
对于 \(80\%\) 的数据，\(n,m\leq 10^5\) 。
对于 \(100\%\) 的数据，\(n,m\leq 5\times 10^5\) 。
考场上想复杂了这个最小次数真的很误导人
其实就是简单的拓扑记下每个点累计的反转次数
奇数的反转次数才是真的会反转
这个题主要是要在判环上注意一下
对于这种情况要先跑一下反图看是不是遍历不到的点都是正面
如果不是则输出\(-1\)(推一下即可)
如果都是\(1\)
则可以重建图(只包含上能便利到的点)
再跑\(topo\)就行
std:
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+9;
int n,m,ans;
bool a[N];
int h[N],ver[N],ne[N],idx;
int ind[N];
void add(int u,int v)
{
idx++,ver[idx] = v,ne[idx] = h[u];h[u] = idx;
}
struct E
{
int u,v;
}e[N];
bool b[N];
queue<int> q;
int f[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
for(int i = 1;i <= m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[i].u = u,e[i].v = v;
add(v,u);
ind[u]++;
}
for(int i = 1;i <= n;i++)
if(!ind[i])q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = h[u];i;i = ne[i])
{
int v = ver[i];
if(!--ind[v])q.push(v);
}
}
for(int i = 1;i <= n;i++)
{
if(ind[i])
{
if(!a[i])return printf("-1"),0;
b[i] = 1;
}
}
memset(h,0,sizeof h);
idx = 0;
memset(ind,0,sizeof ind);
for(int i = 1;i <= m;i++)if(!b[e[i].u]&&!b[e[i].v])add(e[i].u,e[i].v),ind[e[i].v]++;
for(int i = 1;i <= n;i++)
if(!ind[i])q.push(i);
while(!q.empty())
{
int u = q.front();
if(f[u]%2)a[u] ^= 1;
if(!a[u])f[u]++,ans++;
q.pop();
for(int i = h[u];i;i = ne[i])
{
int v = ver[i];
f[v] += f[u];
if(!--ind[v])q.push(v);
}
}
printf("%d",ans);
return 0;
}
九点
题目内容:
你需要构造一个 \(1\) 到 \(n\) 的排列 \(p\) 。
有 \(m\) 条限制，每条限制有两个参数 \(x,y\) ，你要保证 \(p_x=y\) 或 \(p_y=x\) 。
求总方案数对 \(998244353\) 取模的结果。
输入格式:
\(n\) \(m\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(x_3\) \(y_3\)
\(......\)
\(x_m\) \(y_m\)
输出格式:
一行一个整数，表示答案。
样例1
putin
5 5
1 2
3 4
3 4
5 3
4 5
putout
2
样例2
putin
4 3
1 2
3 4
4 4
putout
0
提示:
对于 \(30\%\) 的数据，\(n,m\leq 10\) 。
对于 \(60\%\) 的数据，\(n,m\leq 2000\) 。
对于 \(100\%\) 的数据，\(n,m\leq 5\times 10^5\) 。
标签：10,putin,idx,int,样例,day2,leq,学堂,清北 From： https://www.cnblogs.com/AC7-/p/16900002.html