头像

楚天

AFO大学见




离线:23小时前



楚天
29天前
#include<bits/stdc++.h>
using namespace std;
int a;
int main()
{
    cin>>a;
    cout<<a/3600<<":";
    a%=3600;
    cout<<a/60<<":";
    a%=60;
    cout<<a<<endl;
}



楚天
30天前
#include<bits/stdc++.h>
using namespace std;
int n;
int a[2000];
int q[2000];
int hh;
vector<int> g;
int minn;
int main()
{
    cin>>n;
    minn=1e9;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,a[i]);
    }
    cout<<"Minimum value: "<<minn<<endl;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==minn)
        {
            cout<<"Position: "<<i-1;
            break;
        }
    }
    return 0;
}




楚天
30天前
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d,e,f;
double sum;
int main()
{
    cin>>a>>b>>c;
    cin>>d>>e>>f;
    cout<<"VALOR A PAGAR: R$ ";
    printf("%.2lf",b*c+e*f);
}



楚天
30天前

算法流程

1.先进行bfs,找到一条可行的路径,并记录路径,算出到$T$的最大流量$d[T]$

2.倒着寻找刚才走过的可行的路径,利用我们记录的$pre$数组,从$T$开始,每次向前走一个点,即$i=ver[pre[i] or 1]$(i是当前所在的点,下同),因为此时又多扩展的可行流是$d[T]$,所以$f[pre[i]]-=d[T],f[pre[i] \ or \ 1]+=d[T]$

那么算法一定是会结束,因为一个图一定存在一个最大流

算法详细流程

【算法详解】

img

这么一个图,求源点1到汇点4的最大流。

第一轮迭代

将1加入队列,然后将$st[1]$设为访问过,把$d[1]$的容量设置为正无穷

然后以$1$为中心,进行扩展,首先到达$4$这个点,因为$4$这个点是汇点,所以直接返回此时的可行流$20$,将$st[4]=1$

下面我们就需要倒着去寻找路径了,也就是下图中紫色的部分

当前点在$4$处,$pre[4]$是从某个点经过编号为$pre[4]$的边,到达4的一个可行流

在这个图中,也就是$1$,从$1——>4$,此时$f[从1到4]-=d[T]$,变成0,$f[从4到1]+=d[T]$,变成20。

我们的最大流加上$d[T]=20$

接着进行第二轮迭代

首先清空$st$数组,将1加入队列,把$st[1]$设为1,$d[1]$设为正无穷。

以1为中心,向四周进行$bfs$,首先遇到4,虽然4没有被访问过,但是由于$f[从1到4]=0$,所以从1到4不是一个可行流,跳过4号点。然后遇到了$2$,$2$没有被访问过,并且$f[从1到2]>0$目前是一条可行流,进行拓展,把$2$加入队列,并记录路径$pre[2]=$从$1$到$2$的边的标号,$1$弹出队列

接着以$2$为中心,向四周进行$bfs$,首先遇到了$4$,$4$没有被访问过,并且$f[从2到4]>0$,直接返回此时的流量$20$,

下面的过程跟上面的一样,当前的点在$4$处,根据$pre$数组找路径,可以知道是从2号点转移过来的,所以$f[从2到4]-=d[T]$,$f[从4到2]+=d[T]$,从1到2的边流量也这样进行更新

如图所示

第三轮迭代同理,总是找到当前的可行流,然后更新经过路径上的$f[ \ ]$数组......

最后一定会结束迭代

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int ver[N],head[N],ne[N];
int f[N],d[N];
int idx;
int S,T;
int n,m;
int st[N],pre[N];
#define INF 0x3f3f3f3f
void add(int a,int b,int c)
{
    f[idx]=c,ver[idx]=b,ne[idx]=head[a],head[a]=idx++;
    f[idx]=0,ver[idx]=a,ne[idx]=head[b],head[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    q.push(S);
    d[S]=INF;
    memset(st,false,sizeof(st));
    st[S]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=head[t];i!=-1;i=ne[i])
        {
            int j=ver[i];
            if(!st[j]&&f[i])
            {
                st[j]=1;
                d[j]=min(d[t],f[i]);
                pre[j]=i;
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}

int EK()
{
    int r=0;
    while(bfs())
    {
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            f[pre[i]]-=d[T];
            f[pre[i]^1]+=d[T];

        }
        r+=d[T];
    }
    return r;
}
int main()
{
     scanf("%d%d%d%d", &n, &m, &S, &T);
  memset(head, -1, sizeof head);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }

  printf("%d\n", EK());
  return 0;
}


活动打卡代码 AcWing 2171. EK求最大流

楚天
30天前
#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int ver[N],head[N],ne[N];
int f[N],d[N];
int idx;
int S,T;
int n,m;
int st[N],pre[N];
#define INF 0x3f3f3f3f
void add(int a,int b,int c)
{
    f[idx]=c,ver[idx]=b,ne[idx]=head[a],head[a]=idx++;
    f[idx]=0,ver[idx]=a,ne[idx]=head[b],head[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    q.push(S);
    d[S]=INF;
    memset(st,false,sizeof(st));
    st[S]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=head[t];i!=-1;i=ne[i])
        {
            int j=ver[i];
            if(!st[j]&&f[i])
            {
                st[j]=1;
                d[j]=min(d[t],f[i]);
                pre[j]=i;
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}

int EK()
{
    int r=0;
    while(bfs())
    {
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            f[pre[i]]-=d[T];
            f[pre[i]^1]+=d[T];

        }
        r+=d[T];
    }
    return r;
}
int main()
{
     scanf("%d%d%d%d", &n, &m, &S, &T);
  memset(head, -1, sizeof head);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }

  printf("%d\n", EK());

}


活动打卡代码 AcWing 1153. 括号树

楚天
1个月前
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define maxn 500005
int top;
int sta[maxn];
char s[maxn];

using namespace std;
int n;
int head[maxn], ne[maxn], ver[maxn], idx, fa[maxn];
long long lst[maxn], sum[maxn], ans;
void add_edge(int u, int v) {
  ne[idx] = head[u];
  head[u] = idx;
  ver[idx] = v;
  idx++;
}
void dfs(int x) {
  int t = 0;
  if (s[x] == ')') {
    if (top) {
      t = sta[top];
      lst[x] = lst[fa[t]] + 1;
      top--;
    }
  } else if (s[x] == '(') {
    sta[++top] = x;
  }
  sum[x] = sum[fa[x]] + lst[x];
  for (int i = head[x]; i != -1; i = ne[i]) {
    int j = ver[i];
    dfs(j);
  }
  if (t != 0)
    sta[++top] = t;
  else if (top)
    --top;
}
int main() {
  memset(head, -1, sizeof(head));
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = 2; i <= n; i++) {
    int f;
    scanf("%d", &f);
    add_edge(f, i);
    fa[i] = f;
  }
  dfs(1);
  for (int i = 1; i <= n; i++) ans ^= sum[i] * (long long)i;
  printf("%lld", ans);
  return 0;
}



楚天
1个月前
#include<bits/stdc++.h>
using namespace std;
int cnt;
int prime[10000100];
bool vis[1000010];
int main()
{
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)
        vis[j]=1;
    }
    cout<<cnt<<endl;
}



活动打卡代码 AcWing 531. 铺设道路

楚天
1个月前
#include<bits/stdc++.h>
using namespace std;
int h[200000];
int n;
long long ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    for(int i=1;i<=n;i++)
    {
        ans=ans+max(h[i]-h[i-1],0);
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 511. 联合权值

楚天
1个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 400000;
int ne[N], ver[N], idx, head[N];
long long ans;
long long sum;
long long a[N];
int n;
long long res;
const int mod = 10007;
void add(int u, int v) {
  ne[idx] = head[u];
  ver[idx] = v;
  head[u] = idx;
  idx++;
}

void dfs(int x) {
  long long t1 = 0, t2 = 0;
  sum = 0;
  for (int i = head[x]; i != -1; i = ne[i]) {
    int j = ver[i];
    sum = ((sum + a[j]) + mod) % mod;
    if (a[j] > t1) {
      t2 = t1;
      t1 = a[j];
    } else if (a[j] > t2) {
      t2 = a[j];
    }
  }
  ans = max(ans, (long long)t2* t1 );
  for (int i = head[x]; i != -1; i = ne[i]) {
    int j = ver[i];
    res = (res + ((long long)(sum - a[j]) * a[j] % mod) + mod) % mod;
  }
}
int main() {
  memset(head, -1, sizeof(head));
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b);
    add(b, a);
  }
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i++) {
    dfs(i);
  }
  cout <<ans << ' ' << (res + mod) % mod << endl;
  return 0;
}


活动打卡代码 AcWing 1152. 格雷码

楚天
1个月前
#include <bits/stdc++.h>
using namespace std;
long long quick_pow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = (long long)a * a;
    b >>= 1;
  }
  return ans;
}
long long n, k;
int main() {
  cin >> n >> k;
  for (int i = n; i >= 1; i--) {
    if (k > (long long)quick_pow(2, i - 1) - 1) {
      printf("1");
      k = (long long)quick_pow(2, i) - k - 1;
    } else {
      printf("0");
    }
  }
  return 0;
}