萌新求助洛谷题-P3275

常规
1 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n,k;
int start[N], to[N], qz[N], dfn[N], dis[N], dp[N], idx;
bool vis[N],in[N];
inline int read(){
	int r = 0,w = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-'){
			w = -1;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		r = (r << 3) + (r << 1) + (c ^ 48);
		c = getchar();
	}
	return r * w;
}
void addedge(int u, int v, int x)
{
    start[idx] = x;
    to[idx] = v;
    qz[idx] = dfn[u];
    dfn[u] = idx++;
}

bool spfa()
{
    queue<int> q;
    q.push(0);
    dp[0] = 1;
    vis[0] = true;
	for(int i=1;i<=n;i++){
		q.push(i);
		in[i]=1;
		dis[i]=1;
	}
    while (q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int i = dfn[u]; i != -1; i = qz[i])
        {
            int v = to[i];
            if (dis[v] < dis[u] + start[i])
            {
                dis[v] = dis[u] + start[i];
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                    if (++dp[v] > n)
                        return true;
                }
            }
        }
    }
    return false;
}

signed main()
{
    memset(dfn, -1, sizeof dfn);
    n=read();
    k=read();
    for (int i = 1; i <= k; i++){
        int op, a, b;
        op=read();
		a=read();
		b=read();
        if(op == 1){
        	addedge(b, a, 0);
			addedge(a, b, 0);
		}else if(op == 2){
			if(a==b){
				cout<<"-1\n";
				return 0;
			}
			addedge(a, b, 1);
		}else if(op == 3){
			
			addedge(b, a, 0);
		}else if(op == 4){
			addedge(b, a, 1);
			if(a==b){
				cout<<"-1\n";
				return 0;
			}
		}else{
			addedge(a, b, 0);
		}
    }
    for (int i = 1; i <= n; ++i){
    	addedge(0, i, 1);
	}
    if (spfa()){
    	cout<<-1<<"\n";
	}else{
        int s = 0;
        for (int i = 1; i <= n; i++)
            s += dis[i];
        cout<<s<<"\n";
    }
    return 0;
}

网址

4 个赞
2

《真萌新》

3 个赞
3

SPFA

4 个赞
4

%%%，蓝题免谈

4 个赞
5

板子题

差分约束 - OI Wiki (oi-wiki.org)

4 个赞
6

哦对了，其实找不出更好的 SPFA 了。虽然在 op==2 时，可以进一步优化
只能用 Tarjan

SPFA 死了！

4 个赞
7

关于加强版有人用SPFA过了这件事

4 个赞
8

#include #include #include

using namespace std;

int main() { int N, M; cin >> N >> M;
vector A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
}

sort(A.begin(), A.end());

int left = 0, right = A[N-1] - A[0];
while (left < right) {
int mid = left + (right - left) / 2;
int count = 1;
int prev = A[0];
for (int i = 1; i < N; i++) {
if (A[i] - prev >= mid) {
count++;
prev = A[i];
}
}
if (count >= M) {
left = mid + 1;
} else {
right = mid;
}
}

cout << left - 1 << endl;

return 0;

试试吧，我没试过样例

3 个赞
9

补充：include为
#include
#include
#include

3 个赞
10

满级人类之《萌新一哥》

3 个赞
11

我确实是萌新啊\cf

2 个赞
12

你萌新，你都上提高组了

1 个赞
13

吓老子一跳

1 个赞
14

我只是一个连 SPFA 都优化不好的萌新

2 个赞
15

做人不可以太谦虚

2 个赞