Super Monkey

强连通分量+缩点

2020-05-15

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> g[N],id[N];
int n,m;
int low[N],dfn[N],st[N],instack[N],belong[N],in[N],tot=0,cnt=0,scc=0;
void tarjan(int x)
{
    int v;
    low[x]=dfn[x]=++tot;
    st[++cnt]=x;
    instack[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        v=g[x][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(instack[v])
        {
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x])
    {
        scc++;
        do{
            v=st[cnt--];
            instack[v]=0;
            belong[v]=scc;
            id[scc].push_back(v);
        }while(x!=v);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(dfn,0,sizeof dfn);
    cin>>n>>m;
    int u[N],v[N];
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=m;i++)//缩点
    {
        if(belong[u[i]]==belong[v[i]])continue;
        in[belong[v[i]]]++;
    }
    for(int i=1;i<=scc;i++)
        sort(id[i].begin(),id[i].end());
    int sum=0,ans[N];
    for(int i=1;i<=scc;i++)
    {
        if(!in[i])
        {
            sum++;
            ans[sum]=id[i][0];
        }
    }
    printf("%d\n",sum);
    for(int i=1;i<=sum;i++)
    {
        printf("%d ",ans[i]);
    }
}

如何优雅的使用chrome浏览器

2020-03-13

技术分享

chrome浏览器上有很多非常好用的插件，但是chrome浏览器在中国使用有些“水土不服”，那么如何才能优雅的去使用他呢，以下是我解决采用的一些方法。

首先我们要知道下载了chrome并不意味着你就可以用google上网了，这是两码事。

第一步：下载chrome浏览器并安装，这是官方链接。https://www.google.cn/intl/zh-CN/chrome/

第二步：安装google访问助手，并解压。
https://pan.baidu.com/s/14oEmMSKOMXAD9hOrEfgylw
提取码：rrp7
解压之后找到浏览器的设置-扩展程序-开启开发者模式的选项，点解上面的加载已解压的扩展程序，找到刚才的文件夹。

第三步：利用刚刚安装好的google助手插件访问chrome网上应用商店并下载谷歌上网助手（这个下载之后可以把刚刚安好的那个访问助手给删除了），然后根据提示进行登录或注册账号，搞完之后就可以愉快的使用google搜索和chrome网上应用商店拉。

01背包问题

2020-03-12

基础算法

问题描述

有N件物品和一个容量为V的背包。第i件物品的价值是c[i]，重量是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。每种物品只有一件，可以选择放或者不放。

思路

首先定义状态转移方程dp[i] [j]为在容量为j的背包中放入前i件物品，所具有的最大价值。

当背包足够装下某一个物品时，对于这个物品都有放与不放两种状态，对应的状态转移方程为：

$dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]$

code

#include <iostream>

using namespace std;

int n,v,c[1000000],w[1000000];
int dp[105][1005];
int main()
{
    cin >> v >> n;
    for(int i=1; i<=n; i++)
        cin >> c[i] >> w[i];
    

    for(int i=1; i<=n; i++) //物品 
        for(int j=v; j>=0; j--) //容量 
        {
            if(j >= w[i]) //当背包剩余容量大于此物品时 
                dp[i][j] = max(dp[i-1][j-w[i]]+c[i], dp[i-1][j]);
            else      //当背包剩余容量小于此物品时
                dp[i][j] = dp[i-1][j];           
        }
    cout << dp[n][v] << endl;
    return 0;

}