2017 ACM-ICPC Asia Regional Urumqi Online

Posted on | In , | Visitors:

This is my blog.
本场网络赛是我的第一场网络赛，也是和队友第一次的配合，由于某些原因明明没有到场，本蒟篛连代码都搓不出来了，意外地蒙对了规律。此次网络赛在2017-09-09开始，补题龟速中，直到更文时，仍未补完，但会继续学习，争取补完。目前要停更了，高级算法不适合我了，还有得加快速度，国庆节加油啊，尽量补题。
（未完待续）

A. Banana

（不会截长图，那就点链接吧！）
水题。切。
给两个vector，分别表示monkey和banana，如此便可匹配。答案放入set中，避免重复。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
vector<int>monkey[55];
vector<int>banana[55];
set<int>ans;
vector<int>::iterator it;
vector<int>::iterator it2;
set<int>::iterator it3;
int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=1;i<=55;i++){
            monkey[i].clear();
            banana[i].clear();
        }
        int N,M;
        scanf("%d %d",&N,&M);
        for(int i=1;i<=N;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            monkey[x].push_back(y);
        }
        for(int i=1;i<=M;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            banana[x].push_back(y);
        }
        for(int i=1;i<=N;i++){
            if(monkey[i].size()>0){
                ans.clear();
                for(it=monkey[i].begin();it!=monkey[i].end();it++){
                    for(it2=banana[*it].begin();it2!=banana[*it].end();it2++){
                        ans.insert(*it2);
                    }
                }
                for(it3=ans.begin();it3!=ans.end();it3++)
                    printf("%d %d\n",i,*it3);
            }
            
        }
        printf("\n");
    }
    return 0;
}

B. Out-out-control cars

一道几何题，判断两个在运动的三角形是否会相交。可以将一个相对静止，然后判断是否相交。
补题的时候，博博讲了一遍。大致思路就是判断射线和线段是否相交，相交点是否在射线的方向上。我们需要对斜率不存在的进行特殊处理。看起来就很复杂，而且还要算斜率什么的，但是博博思路很清晰，而且直接直播写代码，过了。特别羡慕和敬仰。现在我也会啦，开心！

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Point{
    double x,y;
};
Point a[3],b[3];
double dx1,dy1,dx2,dy2;
// 直线交点函数
int LineIntersect(Point A,Point B,Point C,Point D,double &x,double &y){
    double a1,a2,b1,b2,c1,c2;
    double Delta , Delta_x , Delta_y;
    a1 = B.x - A.x; b1 = C.x - D.x;  c1 = C.x - A.x;
    a2 = B.y - A.y; b2 = C.y - D.y;  c2 = C.y - A.y;
    Delta=a1*b2-a2*b1; Delta_x=c1*b2-c2*b1;Delta_y=a1*c2-a2*c1;
    
    //Delta=0,表示(yb-ya)/(xb-xa)=(yd-yc)/(xd-xc)即两条线平行。
    
    //两直线相交
    if(Delta){
        //设坐标为（A.x+∆x,A.y+∆y),根据相似三角形，可以由AB斜率得∆y=∆x*a2/a1，然后带入CD斜率中，就可以算出∆x得表达式，从而可得如下等式。
        x = A.x+a1*(Delta_x/Delta);
        y = A.y+a2*(Delta_x/Delta);
        return 1; //返回1:    表示两条直线相交,且交点是(x , y)
    }
    //两直线平行
    else{
        //AC、CD平行,即C在AD上，同理，A在CB上
        if(!Delta_x && !Delta_y) return -1; //返回是-1: 表示两条直线是重合关系
        else return 0; //返回0:表示两条直线是平行不相交关系
    }
}
bool judge (Point a[],Point b[],double dx,double dy,int i,int j){
    //两点确定射线
    Point cc;
    cc.x=b[j].x+dx;cc.y=b[j].y+dy;
    
    double xx,yy;
    double maxx,maxy,minx,miny;
    
    //判断线段和射线是否相交，并返回相交点坐标(xx,yy)
    int ins = LineIntersect(a[i],a[(i+1)%3],b[j],cc,xx,yy);
    
    maxx = max(a[i].x,a[(i+1)%3].x);
    maxy = max(a[i].y,a[(i+1)%3].y);
    minx = min(a[i].x,a[(i+1)%3].x);
    miny = min(a[i].y,a[(i+1)%3].y);
    double t = (xx-b[j].x)/dx;
    if (ins==1&&t>0&&(minx<=xx&&xx<=maxx)&&(miny<=yy&&yy<=maxy))//相交，是正向的，在线段内
        return true;
    else
        return false;
}
int main(){
    int casee = 0;
    int T;
    scanf("%d",&T);
    while (T--){
        for (int i=0;i<3;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        scanf("%lf%lf",&dx1,&dy1);
        for (int i=0;i<3;++i) scanf("%lf%lf",&b[i].x,&b[i].y);
        scanf("%lf%lf",&dx2,&dy2);
        
        //相对速度
        dx2-=dx1;
        dy2-=dy1;
        
        bool f = false;
        for (int i=0;i<3&&!f;++i){
            for (int j=0;j<3&&!f;++j){
                if (judge(a,b,dx2,dy2,i,j))//判断a[i]与a[(i+1)%3]构成的线段与b[j]和（dx2-dx1,dy2-dy1)方向的射线是否相交
                    f = true;
            }
        }
        if (f)
            printf("Case #%d: YES\n",++casee);
        else
            printf("Case #%d: NO\n",++casee);
    }
    return 0;
}

C. Coconut

水题。切。
模拟一遍，就可以。

AC代码

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include<cstdio>
using namespace std;
int c[1005];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,b,sum=0,i,flag=0;
        scanf("%d %d",&n,&b);
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(i=1;i<=n-1;i++){
            int d;
            scanf("%d",&d);
            if(!flag){
                sum+=c[i];
                sum-=b*d;
                if(sum<0){
                    flag=1;
                }
            }
        }
        if(!flag){
            printf("Yes\n");
        }
        else
            printf("No\n");
    }
    return 0;
}

小记

犯了个错误，sum<0后，我加了个break，本想剪短时间，却忘记多组数据，如果不把数据读完，会造成遗留数据作为下一组数据内容，估计也只有我会犯这个错误吧！

D. Hack Portals

题目还未曾看！惊悚！

E. Half-consecutive Numbers

icpc21

打表思路一

\(\frac{r*(r+1)}{2}=k^2\quad(\forall k\in\mathbb N)\)
除了1以外,\(r!=\frac{r+1}{2}\(且\(r+1!=\frac{r}{2}\),
如果r是奇数,那么\(\frac{r+1}{2}\)和r是完全平方数；
所以\(\frac{r+1}{2}=\frac{i^2+1}{2}\)是完全平方数，且\(r=i^2\),
如果r是偶数,那么\(\frac{r}{2}\)和\(r+1\)是完全平方数；
所以\(\frac{r+1-1}{2}=\frac{i^2-1}{2}\)是完全平方数，且\(r=i^2-1\),

打表思路二

1 8 49 288 1681 9800
\((1*1)^2\) \((2*3)^2\) \((5*7)^2\) \((12*17)^2\) \((29*41)^2\) \((70*99)^2\)

我们会发现第一个数字是前面的第一个和第二个数字之和，而第二个数字是第一个数字的平方的两倍加减一，当为第偶数个时，减一；当为第奇数个时减一。我们现在找到了我们的了我们的k了，于是乎，我们即可以求出r了。

打表思路三

转自一个dalao的博客
其实我没有看懂，但是我知道他的递推式好厉害啊！
\(r_1=0,r_2=1,r_{n+2}=6*r_{n+1}-r_n+2\)
数学的感觉很重要呐！！！

经过测试，我觉得第二个更快，也可能是第一个思路更正常吧！（我只测了一和二，dalao的那个不知道是怎么推出来的，看他的解释看不懂啊！！欢迎来给我讲解呢！

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
ll a[25]={1,8,
    49,
    288,
    1681,
    9800,
    57121,
    332928,
    1940449,
    11309768,
    65918161,
    384199200,
    2239277041,
    13051463048,
    76069501249,
    443365544448,
    2584123765441,
    15061377048200,
    87784138523761,
    511643454094368,
    2982076586042449};
int main(){
//    ll x=1,y=1;
//    int flag=1;
//    for(ll i=1;i<=20;i++){
//        ll xx=x+y;
//        y=sqrt(xx*xx*2+flag);
//        x=xx;
//         if(i%2)
//         cout<<xx*xx*2<<endl;
//        else  cout<<xx*xx*2-1<<endl;
//        cout<<(ll)(x*y*sqrt(2.0))<<endl;
//        flag*=-1;
//    }
//
    int T;
    scanf("%d",&T);
    int cas=1;
    while(T--){
        long long n;
        scanf("%lld",&n);
        for(int i=0;i<=21;i++){
            if(a[i]>=n){
                printf("Case #%d: %lld\n",cas++,a[i]);
                break;
            }
        }
    }
    return 0;
}

小记

判断是否是完全平方时，用sqrt函数后，需要将其强制转换成int类型后，再平方。

F. Islands

有N个岛，M条路，问你需要新建多少条路，才可以使每两个岛都可以互相通路。即求构成一个强连通图最少需要增加的边。Tarjan算法求出强联通分量之后缩点成一个DAG图。然后，求出a为入度为0的点的数量和b为出度为0的点的数量，取最大值就是答案了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=1e4+10;
int n,m;
int _in,_out;
int flag[maxn];
vector<int>edge[maxn];
stack<int>s;
int dfn[maxn],low[maxn];
int num,cnt;
int in[maxn],out[maxn];
void dfs(int u){
    dfn[u]=low[u]=++num;
    s.push(u);
    for(int i=(edge[u].size()-1);i>=0;i--){
        int v=edge[u][i];
        if(!dfn[v]){
            dfs(v);
            if(low[v]<low[u])
                low[u]=low[v];
        }
        else if(!flag[v]&&dfn[v]<low[u]){
            low[u]=dfn[v];
        }
    }
    if(low[u]==dfn[u]){
        cnt++;//连通图的个数
        while(true){
            int v=s.top();
            s.pop();
            flag[v]=cnt;
            if(v==u) break;
        }
    }
    return ;
}
void Tarjan(){
    memset(flag,0,sizeof(flag));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    num=0;cnt=0;_in=0;_out=0;
    
    for(int i=1;i<=n;i++){
        if(!dfn[i]) dfs(i);
    }
    
    return ;
}
void add_edge(){
    for(int i=1;i<=n;i++){
        for(int j=(edge[i].size()-1);j>=0;j--){
            if(flag[i]!=flag[edge[i][j]])
               ++out[flag[i]],++in[flag[edge[i][j]]];
        }
    }
    for(int i=1;i<=cnt;i++){
        if(!in[i]) _in++;
        if(!out[i]) _out++;
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
            edge[i].clear();
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            edge[u].push_back(v);
        }
        Tarjan();
        if(cnt==1)puts("0");
        else{
            add_edge();
            int ans=max(_in,_out);
            printf("%d\n",ans);
        }
    }
    return 0;
}

G. Query on a string

给你两个字符串，A和B，有两种操作：一种是询问在A的l到r区间内，出现多少次B；第二种是把A中的第x个字母更改为指定字母。
数据范围很小，暴力+树状数组维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn1=1e5+10;
const int maxn2=15;
char s[maxn1],t[maxn2];
int tree[maxn1],flags[maxn1];
int lens;
int lowbit(int x){
    return x&(-x);
}
void change(int x,int p){
    while(x<=lens){
        tree[x]+=p;
        x+=lowbit(x);
    }
    return ;
}
int sum(int k){
    int sum=0;
    while(k>0){
        sum+=tree[k];
        k-=lowbit(k);
    }
    return sum;
}
int find(int l,int r){
    return sum(r)-sum(l-1);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(flags,0,sizeof(flags));
        memset(tree,0,sizeof(tree));
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        scanf("%s",t+1);
        lens=strlen(s+1);
        int lent=strlen(t+1);
        
        for(int i=1;i<=lens-lent+1;i++){
            bool flag=true;
            for(int j=1;j<=lent;j++){
                if(s[i+j-1]!=t[j]){
                    flag=false;
                    break;
                }
            }
            if(flag){
                flags[i+lent-1]++;
                change(i+lent-1,1);
            }
        }
        
        for(int i=1;i<=n;i++){
            char c;
            scanf(" %c",&c);
            if(c=='Q'){
                int l,r;
                scanf("%d %d",&l,&r);
                int ans=max(0,find(l+lent-1,r));
                printf("%d\n",ans);
            }
            else{
                int x;
                scanf("%d %c",&x,&c);
                s[x]=c;
                for(int i=max(1,x-lent+1);i<=x;i++){
                    bool flag=true;
                    for(int j=1;j<=lent;j++){
                        if(s[i+j-1]!=t[j]){
                            flag=false;
                            break;
                        }
                    }
                    if(flag&&!flags[i+lent-1]){
                        flags[i+lent-1]++;
                        change(i+lent-1,1);
                    }
                    if(!flag&&flags[i+lent-1]){
                        flags[i+lent-1]--;
                        change(i+lent-1,-1);
                    }
                }
            }
        }
        printf("\n");
    }
    return 0;
}

H. Skiing

有占据点，有些占据点之间有路，有些没有，需从一个占据点到另一个占据点，且每次只能从高处向低处滑，问最长能滑多少。

思路一

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct ty{
    int v;
    int l;
    ty(){}
    ty(int x,int y):v(x),l(y){}
};
const int maxn=10005;
int q[maxn];
int a[maxn];
int f[maxn];
int ans,n,m,l,r;
vector<ty>path[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(f, 0, sizeof(f));
        memset(q, 0, sizeof(q));
        memset(a, 0, sizeof(a));
        ans=0;l=r=0;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
            path[i].clear();
        for(int i=1;i<=m;i++){
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            path[x].push_back(ty(y,z));
            a[y]++;
        }
        for(int i=1;i<=n;i++){
            if(a[i]==0)
                q[++r]=i;
        }
        
        while(l!=r){
            l++;
            int u=q[l];
            for(int i=0;i<path[u].size();i++){
                int v=path[u][i].v;
                int l=path[u][i].l;
                f[v]=max(f[v],f[u]+l);
                ans=max(f[v],ans);
                a[v]--;
                if(!a[v])
                    q[++r]=v;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路二

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct node{
    int to,val,next;
}e[100010];
int n,m,x,y,val,cnt ;
int IN[10010],head[10010] ;
ll dis[10010];
queue <int> Q ;
void add(int x,int y,int v){
    e[cnt] = (node){ y,v,head[x] } ;
    head[x] = cnt++;
}
void SPFA(int s){
    int u,v;
    Q.push(s);
    while(!Q.empty()){
        u=Q.front() ;
        Q.pop() ;
        for(int i=head[u];~i;i=e[i].next){
            v=e[i].to;
            if(dis[v]<dis[u]+e[i].val){
                dis[v]=dis[u]+e[i].val;
                Q.push(v);
            }
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(IN,0,sizeof(IN));
        memset(head,-1,sizeof(head));
        memset(dis,0,sizeof(dis));
        cnt=0;
        scanf("%d%d",&n,&m) ;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&val);
            add(x,y,val);
            IN[y]++;
        }
        if(n==1){
            printf("0\n");
            continue;
        }
        for(int i=1;i<=n;i++){
            if(IN[i]==0)
                SPFA(i);
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,dis[i]);
        }
        printf("%lld\n",ans);
    }
    return 0 ;  
}

小记

其实觉得两种很像么，第一种手动写队列，第二种用了STL，但从原理和思路来说还是有点不同的。

I. Colored Graph

题目还未曾看！惊悚！

J. Out Journey of Dalian Ends

你需从大连到上海再到西安，但是高铁的路线只有给出可以使用，输出最短的长度，若不能完成，则输出-1。题解中说这是最小费用最大流的问题。以中间点为新起点，所求即分别到达原起点和原终点的两条点不相交的最短路径之和，使用费用流解决。所以最近在看EK问题，还在学习中，期待下次完善此博文。
每个城市拆成出点和入点，源点连西安和大连，汇点连上海，相当于求从西安到上海和从大连到上海最小距离之和，每个城市入点和出点之间连一条容量为1的边，但是注意，上海的容量必须是2，再根据给出的边，分别连接出点入点，存入相应花费，那么问题就可以转化成最小费用最大流了，如果流量不为2输出-1，否则输出最小花费。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<string>
using namespace std;
#define ll long long
const ll maxm = 1e4+5;
const ll INF = 0x3f3f3f3f;
struct node{
    ll u, v, flow, cost, next;
}edge[maxm * 10];
ll cnt, s, t, n, m,COST,FLOW;
ll head[maxm * 10], dis[maxm * 10], pre[maxm * 10];
void init(){
    cnt = 0;//edgenum
    s = 0;//超级源点
    t = n * 5 + 1 ;//超级汇点
    memset(head, -1, sizeof(head));
}
void add(ll u, ll v, ll flow, ll cost){
    node E1={u,v,flow,cost,head[u]};
    edge[cnt]=E1;head[u]=cnt++;
    node E2={v,u,0,-cost,head[v]};
    edge[cnt]=E2;head[v]=cnt++;
}
ll bfs(){
    queue<ll>q;
    for (ll i = 0;i <= t;i++) dis[i] = INF;
    //memset(dis,INF,sizeof(dis));//不可以用
    memset(pre, -1, sizeof(pre));
    dis[s] = 0, q.push(s);
    while (!q.empty()){
        ll u = q.front();q.pop();
        for (ll i = head[u];i != -1;i = edge[i].next){
            ll v = edge[i].v;
            if (dis[v] > dis[u] + edge[i].cost&&edge[i].flow){
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i, q.push(v);
            }
        }
    }
    if (dis[t] == INF) return 0;
    return 1;
}
ll MCMF(){
    COST = FLOW=0;
    while (bfs()){
        ll minflow = INF;
        for (ll i = pre[t];i != -1;i = pre[edge[i].u])
            minflow = min(minflow, edge[i].flow);
        for (ll i = pre[t];i != -1;i = pre[edge[i].u])
            edge[i].flow -= minflow, edge[i ^ 1].flow += minflow;
        COST += dis[t] * minflow;
        FLOW += minflow;
    }
    return COST;
}
void getmap(){
    char a[maxm], b[maxm];
    ll k,c,sum=0;
    ll nn = n * 2;
    map<string, ll>p;
    for (ll i = 1;i <= n;i++){
        scanf("%s%s%lld", a, b, &c);
        if (p[a] == 0){
            p[a] = ++sum, k = 1;
            if (strcmp(a, "Shanghai") == 0) k = 2;
            add(p[a], p[a] + nn, k, 0);
        }
        if (p[b] == 0){
            p[b] = ++sum, k = 1;
            if (strcmp(b, "Shanghai") == 0) k = 2;
            add(p[b], p[b] + nn, k, 0);
        }
        ll u = p[a], v = p[b];
        add(u + nn, v, INF, c);
        add(v + nn, u, INF, c);
    }
    ll u = p["Dalian"];
    add(s, u, 1, 0);
    u = p["Xian"];
    add(s, u, 1, 0);
    u = p["Shanghai"];
    add(u + nn, t, 2, 0);
    return ;
}
int main(){
    ll T;
    scanf("%lld", &T);
    while (T--){
        scanf("%lld", &n);
        init();
        getmap();
        MCMF();
        if (FLOW == 2) printf("%lld\n", COST);
        else printf("-1\n");
    }
    return 0;
}

小记

寻找i^1是什么意思

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<i<<" "<<(i^1)<<endl;
    }
    return 0;
}
//偶数+1，奇数-1
//因为每次进入edge数组的点都是成对的，所以可以将这两个互连的点进行反向连接

注
不知道为什么E题部分公式不对了，算了，就这样吧。有时间改吧！还得会改啊！很机智的想到我这里预览是对的，所以截图啦！ 真的觉得自己菜死，怎么现场写不出代码来呢！需要锻炼锻炼，包括胆量，还有实力啦！希望我不是拖后腿的那个。今天晚上是选拔CCPC的比赛，其实看前几次网络赛，我总觉得我们队会被淘汰，但这样是不对的，好紧张啊。尽力吧！（嘻嘻，拿到名额，满血复活，更有动力啦） 然后周末两天还是满满的网络赛。（菜死，半天在干别的事情之后，就没有精力了，还陷入一道题中无法自拔；尤其看到博博一个人撑起队伍，真的是惭愧至极） 不知道我什么时候可以补完题目，希望加油啦！ 然后ll开了个深度学习的讲座，机器学习看起来很高深呢！打算去听听，若有所获，我应该会写一点点东西吧！ 总之想学的很多，没学的很多。 然后感觉最近状态不好，心不在焉，课业有些落下了，得补一补了。 然后希望能在一点前睡觉啊，貌似会猝死的。 然后最近好像忘记了一个人，因为一个人。哎，烦！学习学习去。 最后新收藏了一个歌单，甜甜的歌，哇！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽