QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#328420 | #5048. All Pair Maximum Flow | zhouhuanyi | WA | 8ms | 50864kb | C++14 | 3.0kb | 2024-02-15 20:02:52 | 2024-02-15 20:02:53 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 2000000
#define mod 1000000007
using namespace std;
namespace iobuff{
const int LEN=1000000;
char in[LEN+5], out[LEN+5];
char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
inline char gc(void)
{
return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
}
inline void pc(char c)
{
pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
(*pout++)=c;
}
inline void flush()
{ fwrite(out, 1, pout-out, stdout), pout=out; }
template<typename T> inline void scan(T &x)
{
static int f;
static char c;
c=gc(), f=1, x=0;
while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
x*=f;
}
template<typename T> inline void putint(T x, char div)
{
static char s[100];
static int top;
top=0;
x<0?pc('-'), x=-x:0;
while(x) s[top++]=x%10, x/=10;
!top?pc('0'), 0:0;
while(top--) pc(s[top]+'0');
pc(div);
}
}
using namespace iobuff;
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
struct reads
{
int x,y;
long long z;
bool operator < (const reads &t)const
{
return x!=t.x?x>t.x:y<t.y;
}
};
reads tong[N+1],dque[N+1];
struct node
{
int num;
long long data;
bool operator < (const node &t)const
{
return data>t.data;
}
};
priority_queue<node>q;
int n,m,length,tops,deg[N+1],pv[N+1],pvt[N+1],rt[N+1],sz[N+1],ans;
bool used[N+1];
vector<int>E[N+1];
bool cmp(reads a,reads b)
{
return a.z>b.z;
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x),deg[x]++,deg[y]++;
return;
}
int find(int x)
{
if (rt[x]==x) return x;
return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
sz[y]+=sz[x],rt[x]=y;
return;
}
int main()
{
int top,x;
scan(n),scan(m),length=m;
for (int i=1;i<=m;++i)
{
scan(tong[i].x),scan(tong[i].y),scan(tong[i].z);
if (tong[i].x>tong[i].y) swap(tong[i].x,tong[i].y);
}
sort(tong+1,tong+m+1);
for (int i=1;i<=m;++i)
{
if (tong[i].x+1!=tong[i].y)
{
++length,add(i,length),x=tong[i].y;
while (x!=tong[i].x) add(pvt[x],length),x=pv[x];
}
pv[tong[i].y]=tong[i].x,pvt[tong[i].y]=i;
}
for (int i=1;i<=m;++i)
if (deg[i]==1)
q.push((node){i,tong[i].z});
while (!q.empty())
{
top=q.top().num,q.pop();
if (!deg[top]) continue;
used[top]=1,deg[top]=0;
for (int i=0;i<E[top].size();++i)
if (deg[E[top][i]])
{
deg[E[top][i]]=0;
for (int j=0;j<E[E[top][i]].size();++j)
if (E[E[top][i]][j]!=top)
{
deg[E[E[top][i]][j]]--,tong[E[E[top][i]][j]].z+=tong[top].z;
if (deg[E[E[top][i]][j]]==1) q.push((node){E[E[top][i]][j],tong[E[E[top][i]][j]].z});
}
}
}
for (int i=1;i<=m;++i)
if (!used[i])
dque[++tops]=tong[i];
for (int i=1;i<=n;++i) rt[i]=i,sz[i]=1;
sort(dque+1,dque+tops+1,cmp);
for (int i=1;i<=tops;++i) Adder(ans,1ll*sz[find(dque[i].x)]*sz[find(dque[i].y)]%mod*(dque[i].z%mod)%mod),unionn(find(dque[i].x),find(dque[i].y));
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 50696kb
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: 8ms
memory: 50864kb
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:
681004281
result:
wrong answer 1st numbers differ - expected: '858325335', found: '681004281'