QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187484#3855. Regional developmentFlying2018#RE 1ms4116kbC++142.2kb2023-09-24 17:44:412023-09-24 17:44:42

Judging History

你现在查看的是最新测评结果

  • [2023-09-24 17:44:42]
  • 评测
  • 测评结果：RE
  • 用时：1ms
  • 内存：4116kb
查看
  • [2023-09-24 17:44:41]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int N=10010;
typedef long long ll;
namespace dinic{
    const int inf=0x3f3f3f3f;
    int nxt[N<<1],from[N<<1],to[N<<1],w[N<<1],head[N],cur[N],cnt=1,n;
    int add(int u,int v,int w0)
    {
        nxt[++cnt]=head[u],from[cnt]=u,to[cnt]=v,w[cnt]=w0;head[u]=cnt;
        nxt[++cnt]=head[v],from[cnt]=v,to[cnt]=u,w[cnt]=0;head[v]=cnt;
        return cnt;
    }
    int dep[N];queue<int>q;
    bool bfs(int s,int t)
    {
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++) dep[i]=-1,cur[i]=head[i];
        dep[s]=0,q.push(s);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=nxt[i]) if(w[i])
            {
                int v=to[i];
                if(dep[v]==-1) dep[v]=dep[u]+1,q.push(v);
            }
        }
        return dep[t]!=-1;
    }
    int dfs(int u,int t,int flow=inf)
    {
        if(u==t || !flow) return flow;
        int res=0;
        for(int &i=cur[u];i;i=nxt[i]) if(w[i])
        {
            int v=to[i],f;
            if(dep[v]==dep[u]+1 && (f=dfs(v,t,min(flow,w[i]))))
            {
                w[i]-=f,w[i^1]+=f;
                flow-=f,res+=f;
                if(!flow) break;
            }
        }
        return res;
    }
    ll solve(int s,int t){ll r=0;while(bfs(s,t)) r+=dfs(s,t);return r;}
}
int x[N],y[N],w[N],id[N],s0,t0;ll deg[N];
int main()
{
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    s0=n+1,t0=s0+1;dinic::n=t0;
    ll res=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&w[i]);
        deg[x[i]]-=w[i],deg[y[i]]+=w[i];
        id[i]=dinic::add(y[i],x[i],1);
    }
    for(int i=1;i<=n;i++) if(deg[i]>0) dinic::add(s0,i,deg[i]/k),res+=deg[i]/k;
    else if(deg[i]<0) dinic::add(i,t0,-deg[i]/k);
    ll ans=dinic::solve(s0,t0);
    if(res!=ans){puts("IMPOSSIBLE");return 0;}
    else
    {
        for(int i=1;i<=m;i++) if(dinic::w[id[i]]==1) printf("%d\n",w[i]-k);
        else printf("%d\n",w[i]);
    }
    return 0;
}
/*
5 6 5
1 2 2
1 3 3
3 2 3
2 4 2
5 4 3
5 2 2
*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

10 23 3
2 10 1
2 6 1
6 9 1
7 9 1
6 7 1
3 6 1
1 3 1
1 6 2
6 10 1
2 9 1
4 9 2
4 7 2
3 10 2
3 9 1
6 8 1
7 8 2
3 5 1
5 9 1
8 9 2
3 8 2
1 5 2
1 4 1
5 10 2

output:

-2
1
1
1
1
1
-2
2
1
1
-1
2
-1
-2
1
2
1
-2
2
-1
-1
1
2

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

100 1297 11
27 34 5
7 34 6
7 90 3
80 90 6
37 80 6
37 48 5
47 48 6
47 86 5
56 86 6
56 84 5
63 84 6
38 63 6
66 91 8
12 91 6
12 15 5
15 22 1
22 87 5
46 87 6
46 63 10
63 87 8
71 87 6
65 71 6
38 65 1
38 67 4
29 67 6
9 29 6
9 21 5
16 21 6
16 89 2
89 98 5
4 98 6
4 13 4
13 33 5
14 33 6
14 66 10
66 86 10
57 ...

output:

5
6
-8
6
6
5
6
5
6
5
6
6
8
6
5
1
-6
-5
10
8
6
6
1
4
6
6
5
6
-9
5
-5
4
5
6
-1
10
6
6
5
7
6
6
8
5
6
5
5
6
6
5
6
5
6
1
6
3
5
6
5
5
6
8
9
6
8
5
6
5
-6
-5
6
5
6
6
5
6
5
6
6
5
6
5
10
6
7
5
5
-5
7
5
5
6
-5
5
5
6
6
6
-6
5
10
-6
5
6
6
5
5
-4
6
-5
5
5
8
5
-5
-6
5
5
5
-5
5
6
-9
-5
5
6
1
5
-5
5
5
5
6
9
-6
-5
-8...

result:

ok correct plan

Test #3:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

100 1272 18
39 40 14
39 95 4
21 95 14
12 21 14
12 82 16
28 82 14
17 28 14
17 67 5
35 67 14
11 35 1
11 67 15
17 58 4
58 80 4
28 80 14
28 77 3
25 77 10
22 25 14
22 54 4
13 54 14
13 99 4
86 99 14
86 89 16
21 89 14
21 62 4
16 62 14
16 81 4
76 81 14
56 76 1
28 56 14
28 47 4
19 47 14
19 91 4
22 91 14
13 2...

output:

14
4
14
14
-2
14
14
5
14
1
-3
4
4
-4
3
10
14
4
14
-14
14
16
14
4
14
-14
14
1
14
4
14
-14
-4
14
-14
4
14
14
-14
4
13
4
2
-4
4
4
14
4
17
14
4
4
-4
9
-4
4
14
14
17
4
4
14
4
4
4
14
14
4
4
14
14
-14
2
4
9
4
4
-4
10
4
4
-4
-17
14
11
14
-14
14
10
4
8
4
14
-8
14
-4
4
-4
4
14
4
4
14
4
17
-17
17
11
7
11
7
7
-...

result:

ok correct plan

Test #4:

score: 0
Accepted
time: 1ms
memory: 4116kb

input:

100 1350 3
22 75 2
22 50 2
22 35 1
25 35 2
42 76 2
39 42 2
36 39 2
14 36 2
14 33 1
33 72 1
54 72 2
54 73 1
5 73 2
45 92 2
23 92 2
23 26 2
26 62 1
6 62 1
22 86 1
24 86 2
7 24 2
7 55 2
20 39 2
20 73 1
27 73 2
27 68 1
24 68 2
24 98 1
8 98 2
8 33 1
3 33 2
1 3 1
3 97 1
83 97 2
83 90 1
38 90 2
38 86 1
21 ...

output:

-1
2
1
2
2
2
2
2
1
1
2
1
-1
-1
-1
2
1
-2
1
2
2
2
2
-2
-1
1
2
1
2
1
2
1
1
2
1
-1
1
1
2
2
1
1
2
1
1
1
2
1
2
2
1
2
2
1
2
1
1
1
2
2
1
1
2
1
2
-2
2
-1
1
-2
2
2
-2
2
1
2
1
2
2
2
2
-2
-1
2
-2
1
2
1
1
-1
1
1
2
-2
2
1
1
1
1
2
1
-1
1
1
2
1
1
1
1
-1
2
1
1
1
2
1
2
2
-2
2
-2
2
1
2
1
1
2
2
-2
-1
2
1
2
2
2
1
-2
1
...

result:

ok correct plan

Test #5:

score: -100
Runtime Error

input:

1000 9780 26
39 260 1
215 260 25
215 483 1
483 801 1
801 977 1
379 977 25
316 379 25
316 732 1
474 732 25
183 474 25
177 183 25
177 788 1
525 788 25
525 909 1
51 909 25
51 565 1
203 565 25
203 353 1
353 655 8
655 814 1
814 999 1
305 999 25
52 305 25
52 978 20
839 978 25
646 839 25
536 646 25
536 571...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-02-02 01:42:48 | 开源项目