QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#288009 | #5048. All Pair Maximum Flow | zhangtx123 | WA | 4ms | 22540kb | C++14 | 2.4kb | 2023-12-21 15:18:52 | 2023-12-21 15:18:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 400010
int n, m, i, j, k, T;
int sze[N], f[N], u[N], v[N], w[N];
int lst, nw, vis[N], ans, x, y;
set<pair<int, int> >G[N], conv;
vector<pair<int, int> >E;
int fa(int x) {
if(f[x] == x) return x;
return f[x] = fa(f[x]);
}
void del(int i) {
conv.erase({w[i], i});
G[u[i]].erase({v[i], i});
G[v[i]].erase({u[i], i});
}
signed main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
// srand(time(NULL));
// T=read();
// while(T--) {
//
// }
n=read(); m=read();
for(i=1; i<=m; ++i) {
u[i]=read(); v[i]=read(); w[i]=read();
if(u[i] > v[i]) swap(u[i], v[i]);
if(v[i]==u[i]+1 || (u[i]==1 && v[i]==n)) conv.insert({w[i], i}), debug("{%lld %lld}\n", w[i], i);
if(u[i]==1 && v[i]==n) swap(u[i], v[i]);
G[u[i]].insert({v[i], i});
G[v[i]].insert({u[i], i});
}
while(!conv.empty()) {
auto t = *conv.begin();
vis[i=t.se]=1; del(i);
lst=v[i]; nw=u[i];
debug(">> %lld | %lld %lld\n", i, u[i], v[i]);
while(nw!=v[i]) {
debug("%lld %lld\n", lst, nw);
auto it = G[nw].upper_bound({lst, 1e9});
if(it == G[nw].end()) it = G[nw].begin();
j = it -> se;
if(conv.find({w[j], j})==conv.end()) {
debug("============= {%lld %lld}\n", w[j], j);
w[j] += w[i];
conv.insert({w[j], j});
if(u[j] != nw) swap(u[j], v[j]);
}
else del(j), w[j]+=w[i];
debug("find edge(%lld) : %lld -> %lld {%lld %lld}\n", j, v[j], u[j]);
lst = nw; nw = it->fi;
}
}
for(i=1; i<=n; ++i) f[i]=i, sze[i]=1;
for(i=1; i<=m; ++i)
if(!vis[i]) E.pb({w[i], i}), debug("Add %lld [%lld %lld]\n", w[i], u[i], v[i]);
sort(E.begin(), E.end()); reverse(E.begin(), E.end());
for(auto t : E) {
i = t.se;
x = u[i]; y = v[i];
ans += sze[fa(x)]*sze[fa(y)]*w[i];
debug("%lld <-> %lld %lld %lld %lld[%lld %lld] \n", x, y, w[i], fa(x), fa(y), sze[fa(x)], sze[fa(y)]);
sze[fa(y)]+=sze[fa(x)]; f[fa(x)]=fa(y);
}
printf("%lld", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22400kb
input:
6 8 1 2 1 2 3 10 3 4 100 4 5 1000 5 6 10000 6 1 100000 1 4 1000000 1 5 10000000
output:
12343461
result:
ok 1 number(s): "12343461"
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 22540kb
input:
20 30 5 7 9066926 13 15 636587393 1 12 234024833 7 11 863853881 7 9 961926707 12 20 525748907 7 10 217196987 15 20 715248370 17 19 577652480 16 19 78750484 1 2 216519168 2 3 26083428 3 4 381598120 4 5 78513523 5 6 106643887 6 7 20069507 7 8 467260856 8 9 383736316 9 10 400897545 10 11 404258163 11 1...
output:
101681004988
result:
wrong answer 1st numbers differ - expected: '858325335', found: '101681004988'