{"id":437,"date":"2023-03-05T20:17:36","date_gmt":"2023-03-05T12:17:36","guid":{"rendered":"http:\/\/hiycz.cn\/?p=437"},"modified":"2023-03-08T14:36:50","modified_gmt":"2023-03-08T06:36:50","slug":"dfs","status":"publish","type":"post","link":"http:\/\/hiycz.cn\/index.php\/2023\/03\/05\/dfs\/","title":{"rendered":"\u7b2c\u4e09\u7ae0\u7b97\u6cd5\u901f\u5237-\u56fe\u8bba"},"content":{"rendered":"\n

dfs<\/h1>\n\n\n\n

<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
#include<iostream>\nusing namespace std;\nconst int N=10;\nint n;\nint path[N];\/\/\u5b58\u653e\u6bcf\u4e00\u6b65\u7684\u6570\u5b57\nbool vis[N];\/\/\u8868\u793a\u8be5\u6570\u5b57\u662f\u5426\u88ab\u8bbf\u95ee\n\n\nvoid dfs(int u)\n{\n    if(u==n)\/\/u==n\u8868\u793a\u6bcf\u4e00\u6b65\u5df2\u7ecf\u653e\u597d\u4e86\u6570\u5b57\uff0c\u8f93\u51fa\n    {\n        for(int i=0;i<n;i++)cout<<path[i]<<\" \";\n        puts(\"\");\n    }\n    else{\n        for(int i=1;i<=n;i++)\n        {\n            if(!vis[i])\/\/\u5224\u65ad\u6570\u5b57\u662f\u5426\u88ab\u8bbf\u95ee\n            {\n                path[u]=i;\n                vis[i]=true;\n                dfs(u+1);\n                vis[i]=false;\n            }\n        }\n    }\n}\n\n\n\nint main()\n{\n    cin>>n;\n    dfs(0);\n}<\/pre>\n\n\n\n
<\/p>\n\n\n\n
n\u7687\u540e<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
<\/p>\n\n\n\n
#include<iostream>\nusing namespace std;\nconst int  N=30;\nchar m[N][N];\nbool r[N],l[N],x1[N],x2[N];\n\nvoid dfs(int u,int n)\n{\n    \n    if(u==n){\n   \n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<n;j++)\n                cout<<m[i][j];\n            puts(\"\");            \n        }\n        puts(\"\");\n\n    }\n    else{\n        \n        for(int i=0;i<n;i++)\n        {\n            \n            if(!r[u]&&!l[i]&&!x1[u+i]&&!x2[i-u+n-1])\n            {\n                m[u][i]='Q';\n                r[u]=true;\n                l[i]=true;\n                x1[u+i]=true;\n                x2[i-u+n-1]=true;\n                dfs(u+1,n);\n                r[u]=false;\n                m[u][i]='.';\n                l[i]=false;\n                x1[u+i]=false;\n                x2[i-u+n-1]=false;\n            }\n        }\n    }\n}\n\nint main()\n{\n    int n;\n    cin>>n;\n    for(int i=0;i<n;i++)\n        for(int j=0;j<n;j++)\n            m[i][j]='.';\n    dfs(0,n);\n}\n<\/pre>\n\n\n\n
\u9996\u5148\u601d\u8def\uff0c\u4f9d\u6b21\u7ed9\u6bcf\u4e00\u884c\u653e\u7687\u540e\uff0c\u5224\u65ad\u80fd\u5426\u653e\uff0c\u80fd\u653e\u8981\u6ee1\u8db3\u884c\u5217\u5bf9\u89d2\u7ebf\u65e0\u7687\u540e\uff0c\u7136\u540e\u8bbe\u7f6e\u5bf9\u5e94\u6570\u7ec4\u4e3atrue\uff0c\u7136\u540e\u653e\u4e0b\u4e00\u884c\uff0c\u8fd9\u4e2a\u904d\u5386\u540e\u8981\u56de\u6eaf\uff0c\u5373\u628a\u4e4b\u524d\u6539\u53d8\u7684\u53d8\u56de\u53bb<\/p>\n\n\n\n
bfs<\/h2>\n\n\n\n
\u8d70\u8ff7\u5bab<\/a><\/h2>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n\n\n\n
#include<iostream>\n#include<queue>\n#include<algorithm>\n#include<cstring>\nusing namespace std;\ntypedef pair<int,int> PII;\/\/\u5b9a\u4e49\u6253\u5305\uff0c\u8fd9\u4e2a\u8981\u5b66\u4f1a\nint n,m;\nconst int N=110;\nint a[N][N],d[N][N];\n\nint dfs()\n{\n    memset(d,-1,sizeof d);\/\/d\u521d\u59cb\u5316\u4e3a-1\n    d[0][0]=0;\n    queue<PII> q;\n    q.push({0,0});\n    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};\/\/\u7528\u6570\u7ec4\u8868\u793a\u504f\u79fb\n    while(q.size())\n    {\n        PII tmp=q.front();\n        q.pop();\n        for(int i=0;i<4;i++)\n        {\n            int x=tmp.first+dx[i],y=tmp.second+dy[i];\n            if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&a[x][y]==0)\n            {\n                d[x][y]=d[tmp.first][tmp.second]+1;\n                q.push({x,y});\n            }\n        }\n    }\n    return d[n-1][m-1];\n}\n\n\nint main()\n{\n    cin>>n>>m;\n    for(int i=0;i<n;i++)\n        for(int j=0;j<m;j++)scanf(\"%d\",&a[i][j]);\n    cout<<dfs();\n}<\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
#include<iostream>\n#include<queue>\n#include<algorithm>\n#include<cstring>\n#include<unordered_map>\nusing namespace std;\n\nstring s1,s2;\n\nint bfs()\n{\n    queue<string> q;\n    unordered_map<string,int> d;\n    q.push(s1);\n    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};\n    d[s1]=0;\n    s2=\"12345678x\";\n    while(q.size())\n    {\n        auto tmp=q.front();\n        q.pop();\n\n        int sx=tmp.find('x');\n        if(s2==tmp)return d[s2];\n        \n        for(int i=0;i<4;i++)\n        {\n            int x=sx\/3+dx[i],y=sx%3+dy[i];\n            if(x>=0&&y>=0&&x<3&&y<3)\n            {\n                int distance=d[tmp];\n                \/\/ cout<<distance<<endl;\n                swap(tmp[sx],tmp[3*x+y]);\n                if(!d.count(tmp))\n                {\n                    q.push(tmp);\n                    d[tmp]=distance+1;\n                }\n             swap(tmp[sx],tmp[3*x+y]);   \n            }\n            \n            \n        }\n    }\n    return -1;\n    \n}\n\n\nint main()\n{\n    char s[2];\n\n    for (int i = 0; i < 9; i ++ )\n    {\n        cin >> s;\n        s1 += *s;\n    }\n\n    cout << bfs() << endl;\n\n    return 0;\n}<\/pre>\n\n\n\n
\u5173\u4e8e\u90bb\u63a5\u8868\u7684\u5b66\u4e60<\/p>\n\n\n\n
\u4e00\u3001\u9996\u5148 \u5f04\u6e05\u695a \u51e0\u4e2a\u6570\u7ec4\u7684\u542b\u4e49\uff0c\u7136\u540e\u518d\u53bb \u770b \u90bb\u63a5\u8868\u7684\u8868\u793a\u4ee3\u7801\uff0c\u53d1\u73b0\u5bb9\u6613\u7406\u89e3\u4e00\u4e9b\uff0c\u5728\u8fd9\u91cc\u518d\u6b21\u56de\u987e\u4e0b\u51e0\u4e2a\u6570\u7ec4\u7684\u542b\u4e49\uff1a<\/p>\n\n\n\n
h[N] : \u8868\u793a \u7b2c i \u4e2a\u8282\u70b9\u7684 \u7b2c\u4e00\u6761\u8fb9\u7684 idx
ne[M] : \u8868\u793a \u4e0e \u7b2c idx \u6761\u8fb9 \u540c\u8d77\u70b9 \u7684 \u4e0b\u4e00\u6761\u8fb9 \u7684 idx
e[M] : \u8868\u793a \u7b2cidx \u6761\u8fb9\u7684 \u7ec8\u70b9<\/p>\n\n\n\n
N \uff1a \u8282\u70b9\u6570\u91cf
M\uff1a\u8fb9\u7684\u6570\u91cf
i : \u8282\u70b9\u7684\u4e0b\u6807\u7d22\u5f15
idx \uff1a \u8fb9\u7684\u4e0b\u6807\u7d22\u5f15<\/p>\n\n\n\n
\u4e8c\u3001\u7136\u540e\u7ed3\u5408\u4ee3\u7801\u6a21\u7248\u7406\u89e3\u5b9a\u4e49<\/p>\n\n\n\n
\u53d8\u91cf\u521d\u59cb\u5316\u5b9a\u4e49\uff1a<\/p>\n\n\n\n
int h[N], e[M], ne[M], idx;<\/pre>\n\n\n\n

\u5f53\u6211\u4eec\u52a0\u5165\u4e00\u6761\u8fb9\u7684\u65f6\u5019\uff1a<\/p>\n\n\n\n
public static void add(int a,int b){\ne[idx] = b; \/\/ \u8bb0\u5f55 \u52a0\u5165\u7684\u8fb9 \u7684\u7ec8\u70b9\u8282\u70b9\nne[idx] = h[a]; \/\/ h[a] \u8868\u793a \u8282\u70b9 a \u4e3a\u8d77\u70b9\u7684\u7b2c\u4e00\u6761\u8fb9\u7684\u4e0b\u6807\uff0cne[idx] = h[a] \u8868\u793a\u628a h[a] \u8fd9\u6761\u8fb9\u63a5\u5728\u4e86 idx \u8fd9\u6761\u8fb9\u7684\u540e\u9762\uff0c\u5176\u5b9e\u4e5f\u5c31\u662f\u628a a \u8282\u70b9\u7684\u6574\u6761\u94fe\u8868 \u63a5\u5728\u4e86 idx \u8fd9\u6761\u8fb9 \u540e\u9762\uff1b\u76ee\u7684\u5c31\u662f\u4e3a\u4e86\u4e0b\u4e00\u6b65 \u628a idx \u8fd9\u6761\u8fb9 \u5f53\u6210 a \u8282\u70b9\u7684\u5355\u94fe\u8868\u7684 \u7b2c\u4e00\u6761\u8fb9\uff0c\u5b8c\u6210\u628a\u6700\u65b0\u7684\u4e00\u6761\u8fb9\u63d2\u5165\u5230 \u94fe\u8868\u5934\u7684\u64cd\u4f5c\uff1b\nh[a] = idx++; \/\/ a\u8282\u70b9\u5f00\u5934\u7684\u7b2c\u4e00\u6761\u8fb9\u7f6e\u4e3a\u5f53\u524d\u8fb9\uff0cidx\u79fb\u52a8\u5230\u4e0b\u4e00\u6761\u8fb9\n}<\/pre>\n\n\n\n
\u6811\u548c\u56fe\u7684\u6df1\u5ea6\u4f18\u5148\u904d\u5386<\/h1>\n\n\n\n
\/\/\u5bf9\u4e8e\u6bcf\u4e2a\u70b9k,\u5f00\u4e00\u4e2a\u5355\u94fe\u8868\uff0c\u5b58\u50a8k\u6240\u6709\u53ef\u4ee5\u8d70\u5230\u7684\u70b9\uff0ch[k]\u5b58\u50a8\u8fd9\u4e2a\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9\n\/\/    h[N] : \u8868\u793a \u7b2c i \u4e2a\u8282\u70b9\u7684 \u7b2c\u4e00\u6761\u8fb9\u7684 idx\n\/\/\/   ne[M] : \u8868\u793a \u4e0e \u7b2c idx \u6761\u8fb9 \u540c\u8d77\u70b9 \u7684 \u4e0b\u4e00\u6761\u8fb9 \u7684 idx\n\/\/    e[M] : \u8868\u793a \u7b2cidx \u6761\u8fb9\u7684 \u7ec8\u70b9\n\/\/    int h[N],e[N],ne[N],idx;\n\/\/    N \uff1a \u8282\u70b9\u6570\u91cf\n\/\/    M\uff1a\u8fb9\u7684\u6570\u91cf\n\/\/    i : \u8282\u70b9\u7684\u4e0b\u6807\u7d22\u5f15\n\/\/    idx \uff1a \u8fb9\u7684\u4e0b\u6807\u7d22\u5f15\n\n\/\/\u589e\u52a0\u4e00\u6761\u8fb9a->b;\nvoid add(int a,int b)\n{\n\te[idx]=b,ne[idx]=h[a],h[a]=idx++;\n } \n \n \/\/\u521d\u59cb\u5316\n idx=0;\n memset(h,-1,sizeof h);\n \n int dfs(int u){\n \tst[u]=true;\/\/st[u]\u8868\u793au\u5df2\u7ecf\u88ab\u904d\u5386\u8fc7\n\tfor(int i=h[u];i!=-1;i=ne[i])\n\t{\n\t\tint i=0;\n\t\tint j=e[i];\n\t\tif(!st[j])dfs(j);\n\t } \n } <\/pre>\n\n\n\n
\u4f8b\u9898acw846\u6811\u7684\u91cd\u5fc3<\/a><\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
#include<iostream>\nusing namespace std;\n#include<cstring>\n#include <algorithm>\nconst int N=100010,M=2*N;\nint e[M],h[N],ne[M],idx;\/\/h\u8868\u793a\u8be5\u9876\u70b9\u7684\u7b2c\u4e00\u6761\u8fb9\uff0ce[M]\u8868\u793a\u8be5\u8fb9\u7684\u7ec8\u70b9\uff0cne\u8868\u793a\u540c\u8d77\u70b9\u7684\u4e0b\u4e00\u6761\u8fb9\nbool st[N];\n\nint ans=N,n;\n\n\nvoid add(int a,int b)\n{\n    e[idx]=b,ne[idx]=h[a],h[a]=idx++;\n}\n\nint dfs(int u)\n{\n    int size=0;\n    int sum=0;\n    \n    st[u]=true;\n    for(int i=h[u];i!=-1;i=ne[i])\n    {\n        int j=e[i];\n        if(!st[j])\n        {\n            int s=dfs(j);\n            size=max(size,s);\n            sum+=s;\n\n        }\n    }\n    size=max(size,n-sum-1);\n    ans=min(size,ans);\n    return sum+1;\n}\n\n\nint main()\n{\n    cin>>n;\n    memset(h, -1, sizeof h);\n    for(int i=0;i<n-1;i++)\n    {\n        int a,b;\n        scanf(\"%d%d\\n\",&a,&b);\n        add(a,b);\n        add(b,a);\n    }\n    dfs(1);\/\/\u9876\u70b9\u5b9a\u4e49\u7684\u662f1-n\uff0c\u6240\u4ee5\u8981\u4ece1\u5f00\u59cbdfs\uff1b\n    cout<<ans;\n    return 0;\n    \n}<\/pre>\n\n\n\n
\u6811\u548c\u56fe\u7684\u5e7f\u5ea6\u4f18\u5148\u904d\u5386<\/h1>\n\n\n\n
\u6a21\u677f<\/p>\n\n\n\n
##bfs\nqueue<int>q;\nst[1]=true;\/\/\u8868\u793a\u7b2c\u4e00\u4e2a\u8282\u70b9\u88ab\u904d\u5386\u8fc7 \nq.push(1);\/\/\u4ece1\u5f00\u59cb \n\nwhile(q.size())\n{\n\tint t=q.front;\n\tq.pop();\/\/\u51fa\u961f \n\tfor(int i=h[t];i!=-1;i=ne[i])\n\t{\n\t\tint j=e[i];\n\t\tif(!st[j])\/\/\u5c06\u4e0b\u4e00\u6b65\u7684\u70b9\u90fd\u5165\u961f \n\t\t{\n\t\t\tst[j]=true;\n\t\t\tq.push(j);\n\t\t}\n\t}\n } <\/pre>\n\n\n\n
\u4f8b\u9898acw847\u56fe\u4e2d\u70b9\u7684\u5c42\u6b21<\/a><\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
#include<iostream>\nusing namespace std;\n#include<queue>\n#include<cstring>\n#include<algorithm>\n\nconst int N=100010;\nint h[N],ne[N],e[N],idx,d[N];\n\nvoid add(int a,int b)\/\/\u63d2\u5165\n{\n    e[idx]=b;\n    ne[idx]=h[a];\n    h[a]=idx++;\n}\n\nint main()\n{\n    int m,n;\n    cin>>n>>m;\n    memset(h,-1,sizeof h);\/\/\u4e0d\u521d\u59cb\u5316\u4e0b\u9762\u4f1a\u8d85\u65f6\n    memset(d,-1,sizeof d);\/\/\u521d\u59cb\u5316\uff0c\u6ce8\u610f\u4f4d\u7f6e\uff0c\u4e00\u5b9a\u8981\u5148\u521d\u59cb\u5316\n    while(m--)\n    {\n        int a,b;\n        scanf(\"%d%d\\n\",&a,&b);\n        add(a,b);\n    }\n\n    queue<int> q;\n    d[1]=0;\n    q.push(1);\n\n    while(q.size())\n    {\n        int a=q.front();\n        q.pop();\n            \n        for(int i=h[a];i!=-1;i=ne[i])\n        {\n            \/\/ cout<<\"dsdffdfd[a]\";\n            int j=e[i];\/\/\n            if(d[j]==-1){\/\/\u6539\u53d8\u8ddd\u79bb\uff0c\u91cd\u8fb9\u548c\u81ea\u73af\u65e0\u6cd5\u5165\u961f\n                d[j]=d[a]+1;\n                \n                q.push(j);\n            }\n        }\n    }\n    cout<<d[n];\n    \n    \n    \n}<\/pre>\n\n\n\n
\u53e6\u5916\u52a0\u4e00\u79cd\u6211\u7684\u5c1d\u8bd5\uff0c\u76ee\u524d\u65e0\u6cd5\u89e3\u51b3\u81ea\u73af\u95ee\u9898<\/p>\n\n\n\n
#include<iostream>\n#include<cstring>\n#include<queue>\n#include<algorithm>\nusing namespace std;\nconst int N=100010,M=N*2;\nint h[N],ne[M],e[M],idx,d[N];\nbool st[N];\nint n,m;\ntypedef pair<int,int> PII;\n\n\nvoid add(int a,int b)\n{\n    e[idx]=b;ne[idx]=h[a],h[a]=idx++;\n}\n\nint main()\n{\n    \/\/ typedef pair<int,int> PII;\n    \/\/ unordered_map<PII,int> mymap;\n    scanf(\"%d%d\",&n,&m);\n    memset(h,-1,sizeof h);\/\/\u5bf9\u4e0d\u8d77\u6211\u662fSB\u8fd9\u91cc\u662f\u521d\u59cb\u5316h\uff0c\u4f60\u4e0d\u521d\u59cb\u5316\u6c38\u8fdc\u8df3\u4e0d\u51fa\u53bb\n    for(int i=0;i<m;i++)\n    {\n        int a,b;\n        scanf(\"%d%d\",&a,&b);\n        \/\/ if(!mymap[{a,b}])\n        \/\/ {\n        add(a,b);\n            \/\/ mymap[{a,b}]++;\n        \/\/ }\n    }\n\n    st[1]=true;\n    queue<PII> q;\n    q.push({1,0});\n    \/\/\u6ce8\u610f\u4e86\u4f60\u8fd9\u91cc\u5e76\u4e0d\u662f\u548c\u4f60\u60f3\u7684\u4e00\u6837\uff0c\u9996\u5148\u7b2c\u4e00\u6b21\u786e\u5b9e\u5b83\u4eec\u90fd\u662f\u8ddd\u79bb\u4e3a1\uff0c\u4f46\u662f\u7b2c\u4e8c\u6b65\u5462\uff0c\u6bcf\u6b21\u51fa\u961f\u4e00\u4e2a\u8fb9\u8ddd\u79bb\u5c31++\u8fd9\u65f6\u4e0d\u5bf9\u7684\uff0c\u8fd9\u5e76\u4e0d\u662f\u8ddd\u79bb\u53ea\u80fd\u8bf4\u7b2c\u51e0\u4e2a\u88ab\u904d\u5386\u7684\n    memset(d, -1, sizeof d);\n    while(q.size())\n    {\n        PII b=q.front();\n        int dis=b.second;\n        int a=b.first;\n        q.pop();\n        for(int i=h[a];i!=-1;i=ne[i])\n        {\n            int j=e[i];\n            \n            if(!st[j])\n            {\n                st[j]=true;\n                q.push({j,dis+1});\n                d[j]=dis+1;\n            }\n        }\n    }\n    cout<<d[n];\n    \n}\n <\/pre>\n\n\n\n
\u62d3\u6251\u6392\u5e8f<\/h1>\n\n\n\n
bool topsort()\n{\n    int hh = 0, tt = -1;\n\n    \/\/ d[i] \u5b58\u50a8\u70b9i\u7684\u5165\u5ea6\n    for (int i = 1; i <= n; i ++ )\n        if (!d[i])\n            q[ ++ tt] = i;\n\n    while (hh <= tt)\n    {\n        int t = q[hh ++ ];\n\n        for (int i = h[t]; i != -1; i = ne[i])\n        {\n            int j = e[i];\n            if (-- d[j] == 0)\n                q[ ++ tt] = j;\n        }\n    }\n\n    \/\/ \u5982\u679c\u6240\u6709\u70b9\u90fd\u5165\u961f\u4e86\uff0c\u8bf4\u660e\u5b58\u5728\u62d3\u6251\u5e8f\u5217\uff1b\u5426\u5219\u4e0d\u5b58\u5728\u62d3\u6251\u5e8f\u5217\u3002\n    return tt == n - 1;\n}\n<\/pre>\n\n\n\n
<\/p>\n\n\n\n
dijkstra \u7b97\u6cd5<\/h1>\n\n\n\n
int g[N][N];\/\/\u5b58\u50a8\u6bcf\u6761\u8fb9\nint dist[N];\/\/\u5b58\u50a81\u53f7\u70b9\u5230\u6bcf\u6761\u8fb9\u7684\u6700\u77ed\u8ddd\u79bb\nbool st[N];\/\/\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u6700\u77ed\u8def\u5f84\u662f\u5426\u5df2\u7ecf\u786e\u5b9a\uff1b\n\n\/\/\u6c421\u53f7\u70b9\u5230n\u53f7\u70b9\u7684\u6700\u77ed\u8def\uff0c\u5982\u679c\u4e0d\u5b58\u5728\u8fd4\u56de-1 \nint dijkstra()\n{\n\tmemset(dist,0x3f,sizeof dist);\n\tdist[1]=0;\n\tfor(int i=0;i<n-1;i++)\/\/\u5148\u627e\u51fa\u73b0\u5728\u79bb\u7684\u6700\u8fd1\u7684\u4e14\u6ca1\u6709\u653e\u8fdb\u53bb\u7684\u70b9 \n\t{\n\t\tint t=-1;\n\t\tfor(int j=1;j<=n;j++)\/\/\u4e00\u5f00\u59cb\u7684\u65f6\u5019\u4e00\u4e2a\u70b9\u90fd\u6ca1\u6709\uff0c\u5148\u786e\u5b9a\u4e861\u8fd9\u4e2a\u70b9\uff0c\u7136\u540e\u66f4\u65b01\u5230\u5176\u4ed6\u70b9\u7684\u8ddd\u79bb ,\n\t\t    if(!st[j]&&(t==-1||dist[t]>dist[j]))\n\t\t        t=j;\n\t\t\n\t\tfor(int j=1;j<=n;j++)\/\/\u66f4\u65b0\u8ddd\u79bb \n\t\t    dist[j]=min(dist[j],dist[t]+g[t][j]);\/\/\u7b2c\u4e00\u6b21\u5faa\u73af\u52a0\u5165\u4e861\u8fd9\u4e2a\u70b9\uff0c\u7136\u540e\u5f00\u59cb\u66f4\u65b0\u5230\u5176\u4ed6\u70b9\u7684\u8ddd\u79bb \n\t\tst[t]=true; \n\t}\n\tif(dist[n]=0x3f3f3f3f)return -1;\n\treturn dist[n];\n }<\/pre>\n\n\n\n
bellman_ford<\/h1>\n\n\n\n
\u7b97\u6cd5\u601d\u60f3\u904d\u5386\u6240\u6709\u8fb9\uff0c\u904d\u5386k\u6b21\u627e\u5230\u6bd4\u8f83\u6700\u77ed\u8def\u5f84\u4e3ak\u6b65\u7684\u6700\u77ed\u8def\u5f84<\/p>\n\n\n\n
int n,m;\/\/n\u8868\u793a\u70b9\u6570\uff0cm\u8868\u793a\u8fb9\u6570 \nint dist[N],last[N];\/\/dist[x]\u5b58\u50a81\u5230x\u7684\u6700\u77ed\u8def\u5f84 \n\nstruct Edge\n{\n\tint a,b,w;\/\/a\u8868\u793a\u5165\u70b9\uff0cb\u8868\u793a\u51fa\u70b9\uff0cw\u8868\u793a\u6743\u91cd \n}edges[M];\n\n\/\/\u6c421\u5230n\u7684\u6700\u77ed\u8def\u5f84\uff0c\u5982\u679c\u65e0\u6cd5\u4ece1\u8d70\u5230n\uff0c\u5219\u8fd4\u56de-1\uff1b\nint bellman_ford()\n{\n\tmemset(dist,0x3f,sizeof dist);\n\tdist[1]=0;\n\t\n\tfor(int i=0;i<n;i++)\n\t{\n\t\tmemcpy(last,dist,sizeof dist);\/\/\u6709\u65f6\u5019\u4e3a\u4e86\u907f\u514d\u4e32\u8054\uff0c\u5907\u4efd\u4e00\u4e2a\u4e0a\u4e00\u6b21\u7684 \n\t\tfor(int j=0;j<m;j++)\n\t\t{\n\t\t\tint a=edges[j].a,b=edges[j].b,w=edges[i].w;\n\t\t\tif(dist[b]>last[a]+w)\n\t\t\t    dist[b]=last[a]+w; \n\t\t}\n\t } \n\t if(dist[n]>0x3f3f3f3f\/2)return -1;\n\t return dist[n];\n } <\/pre>\n\n\n\n
spfa<\/h1>\n\n\n\n
int n;\/\/\u603b\u70b9\u6570\nint h[N],w[N],e[N],ne[N],idx;\/\/\u90bb\u63a5\u8868\u76f8\u5173\u4fe1\u606f\nint dist[N],cnt[N];\/\/dist\u8868\u793a\u6700\u77ed\u8ddd\u79bb\uff0ccnt\u8868\u793a\u6700\u77ed\u8def\u5f84\u4e0a\u7ecf\u8fc7\u70b9\u6570\nbool st[N];\/\/\u8868\u793a\u5224\u65ad\u662f\u5426\u5728\u961f\u5217\n\n\/\/\u5b58\u5728\u8d1f\u73af\u8fd4\u56detrue,\u5426\u5219\u8fd4\u56defalse\uff1b\nbool spfa()\n{\n\t\/\/\u4e0d\u9700\u8981\u521d\u59cb\u5316dist[]\u6570\u7ec4\n\t\/\/\u539f\u7406\uff1a\u5982\u679c\u67d0\u6761\u6700\u77ed\u8def\u5f84\u4e0a\u6709n\u4e2a\u70b9\uff0c\u90a3\u4e48\u52a0\u4e0a\u81ea\u5df1\u4e4b\u540e\u4e00\u5171\u6709n+1\u4e2a\u70b9\uff0c\u90a3\u4e48\u4e00\u5b9a\u5b58\u5728\u8d1f\u6743\u56de\u8def\n\tqueue<int> q;\n\tfor(int i=1;i<=n;i++)\n\t{\n\t\tq.push(i);\n\t\tst[i]=true;\n\t }\n\t while(q.size())\n\t {\n\t \tauto t=q.front();\n\t\tq.pop();\n\t\tst[t]=false;\n\t\tfor(int i=h[t];i!=-1;i=ne[i])\n\t\t{\n\t\t\tint j=e[i];\n\t\t\tif(dist[j]>dist[t]+w[i])\n\t\t\t{\n\t\t\t\tdist[j]=dist[t]+w[i];\n\t\t\t\tcnt[j]=cnt[t]+1;\n\t\t\t\tif(cnt[j]>=n)return true;\n\t\t\t\tif(!st[j])\n\t\t\t\t{\n\t\t\t\t\tq.push(j);\n\t\t\t\t\tst[j]=true;\n\t\t\t\t}\n\t\t\t}\n\t\t } \n\t  } \n\t  return false;\n } <\/pre>\n\n\n\n
floyd\u7b97\u6cd5<\/h1>\n\n\n\n
#floyd\u7b97\u6cd5\uff0c\u60f3\u8c61\u4e00\u4e0b\u4ee5k\u4f5c\u4e3a\u4e2d\u95f4\u8282\u70b9\u4e0d\u65ad\u4f18\u5316 \nfor(int k=1;k<=n;k++) \n    for(int i=1;i<=n;i++)\n         for(int j=1;j<=n;j++)\n             d[i][j]=min(d[i][j],d[i][k]+d[k][j]);<\/pre>\n\n\n\n
prim\u7b97\u6cd5<\/h1>\n\n\n\n
int n;      \/\/ n\u8868\u793a\u70b9\u6570\nint g[N][N];        \/\/ \u90bb\u63a5\u77e9\u9635\uff0c\u5b58\u50a8\u6240\u6709\u8fb9\nint dist[N];        \/\/ \u5b58\u50a8\u5176\u4ed6\u70b9\u5230\u5f53\u524d\u6700\u5c0f\u751f\u6210\u6811\u7684\u8ddd\u79bb\nbool st[N];     \/\/ \u5b58\u50a8\u6bcf\u4e2a\u70b9\u662f\u5426\u5df2\u7ecf\u5728\u751f\u6210\u6811\u4e2d\n\n\n\/\/ \u5982\u679c\u56fe\u4e0d\u8fde\u901a\uff0c\u5219\u8fd4\u56deINF(\u503c\u662f0x3f3f3f3f), \u5426\u5219\u8fd4\u56de\u6700\u5c0f\u751f\u6210\u6811\u7684\u6811\u8fb9\u6743\u91cd\u4e4b\u548c\nint prim()\n{\n    memset(dist, 0x3f, sizeof dist);\n\n    int res = 0;\n    for (int i = 0; i < n; i ++ )\n    {\n        int t = -1;\n        for (int j = 1; j <= n; j ++ )\n            if (!st[j] && (t == -1 || dist[t] > dist[j]))\n                t = j;\n\n        if (i && dist[t] == INF) return INF;\n\n        if (i) res += dist[t];\n        st[t] = true;\n\n        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);\n    }\n\n    return res;\n}\n<\/pre>\n\n\n\n
Kruskal\u7b97\u6cd5<\/h1>\n\n\n\n
#Kruskal\nint n,m;\/\/n\u4e3a\u70b9\u6570,m\u4e3a\u8fb9\u6570\nint p[N];\/\/\u5e76\u67e5\u96c6\u7684\u7236\u8282\u70b9\u6570\u7ec4 \nstruct Edge\/\/\u5b58\u50a8\u8fb9 \n{\n\tint a,b,w;\n }edges[M];\n bool  cmp(Edge a,Edge b)\n {\n \treturn a.w<b.w;\n  } \n  \n  int find(int x)\/\/\u5e76\u67e5\u96c6\u67e5\u627e \n  {\n  \tif(p[x]!=x)p[x]=find(p[x]);\n  \treturn p[x];\n  }\n  \n  int kruskal()\n  {\n  \tsort(edges,edges+m,cmp);\n  \tfor(int i=1;i<=n;i++);p[i]=i;\/\/\u5e76\u67e5\u96c6\u521d\u59cb\u5316 \n  \tint res=0,cnt=0;\/\/\u6743\u503c\u548c\u8fb9\u6570 \n  \tfor(int i=0;i<m;i++)\/\/\u4e00\u5171m\u6761\u8fb9 \n  \t{\n  \t\tint a=edges[i].a,b=edges[i].b,w=edges[i].w;\n  \t\ta=find(a),b=find(b);\n  \t\tif(a!=b)\/\/\u5224\u65ad\u662f\u5426\u5728\u540c\u4e00\u4e2a\u96c6\u5408\/\/\u4e0d\u5728\u5219\u5408\u5e76 \n  \t\t{\n  \t\t\tp[a]=b;\n  \t\t\tres+=w;\n  \t\t\tcnt++;\n\t\t  }\n\t  }\n\t  if(cnt<n-1)return INF;\n\t  return res;\n  }<\/pre>\n\n\n\n
\u67d3\u8272\u6cd5\u5224\u522b\u4e8c\u5206\u56fe<\/h1>\n\n\n\n
int n;\/\/n\u8868\u793a\u70b9\u6570\nint h[N],e[M],ne[M],idx;\/\/\u90bb\u63a5\u8868\u5b58\u50a8\u56fe\nint color[N];\/\/\u8868\u793a\u6bcf\u4e2a\u70b9\u7684\u989c\u8272\uff0c-1\u8868\u793a\u672a\u67d3\u8272\uff0c0\u8868\u793a\u767d\u8272\uff0c1\u8868\u793a\u9ed1\u8272\n\n\/\/\u53c2\u6570\uff1au\u8868\u793a\u5f53\u524d\u8282\u70b9\uff0cc\u8868\u793a\u5f53\u524d\u989c\u8272\nbool dfs(int u,int c)\n{\n\tcolor[u]=c;\n\tfor(int i=h[u];i!=-1;i=ne[i])\n\t{\n\t\tint j=e[i];\n\t\tif(color[j]==-1)\/\/\u672a\u67d3\u8272\u770b\u4ee5\u540e\u662f\u5426\u51b2\u7a81 \n\t\t{\n\t\t\tif(!dfs(j,!c))return false;\n\t\t}\n\t\telse if(color[j]==c)return false;\/\/\u5df2\u67d3\u8272\u5224\u65ad\u662f\u5426\u76f8\u540c\uff0c\u76f8\u540c\u5219\u51b2\u7a81 \n\t}\n\treturn true;\n } \n bool check()\n {\n \tmemset(color,-1,sizeof color);\n \tbool flag=true;\n \tfor(int i=1;i<=n;i++)\n \t    if(color[i]==-1)\n \t        if(!dfs(i,0))\n \t        {\n \t        \tflag=false;\n \t        \tbreak;\n\t\t\t }\n\treturn flag;\n }<\/pre>\n\n\n\n
\u5308\u7259\u5229\u7b97\u6cd5\u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d<\/h1>\n\n\n\n
int n1,n2;\/\/n1\u8868\u793a\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\u6570\uff0cn2\u8868\u793a\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\u6570 \nint h[N],e[M],ne[M],idx;\nint match[N];\/\/\u5b58\u50a8\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u6bcf\u4e2a\u70b9\u5f53\u524d\u5339\u914d\u7684\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u662f\u54ea\u4e2a\u70b9 \nbool st[N];\/\/\u8868\u793a\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u70b9\u662f\u5426\u88ab\u904d\u5386\u8fc7 \nint find(int x)\n{\n\tfor(int i=h[x];i!=-1;i=ne[i])\n\t{\n\t\tint j=e[i];\n\t\tif(!st[j])\n\t\t{\n\t\t\tst[j]=true;\n\t\t\tif(match[j]==0||find(match[j]))\n\t\t\t{\n\t\t\t\tmatch[j]=x;\n\t\t\t\treturn true;\n\t\t\t}\n\t\t}\n\t}\n\treturn false;\n } \n\/\/\u6c42\u6700\u5927\u5339\u914d\u6570\uff0c\u4f9d\u6b21\u679a\u4e3e\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u70b9\u80fd\u5426\u5339\u914d\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\nint res=0;\nfor(int i;i<=n1;i++)\/\/\u4e5f\u5c31\u662f\u6700\u5927\u5339\u914d\u6570 \n{\n\tmemset(st,false,sizeof st);\n\tif(find(i))res++;\n } int n1,n2;\/\/n1\u8868\u793a\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\u6570\uff0cn2\u8868\u793a\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\u6570 \nint h[N],e[M],ne[M],idx;\nint match[N];\/\/\u5b58\u50a8\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u6bcf\u4e2a\u70b9\u5f53\u524d\u5339\u914d\u7684\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u662f\u54ea\u4e2a\u70b9 \nbool st[N];\/\/\u8868\u793a\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u70b9\u662f\u5426\u88ab\u904d\u5386\u8fc7 \nint find(int x)\n{\n\tfor(int i=h[x];i!=-1;i=ne[i])\n\t{\n\t\tint j=e[i];\n\t\tif(!st[j])\n\t\t{\n\t\t\tst[j]=true;\n\t\t\tif(match[j]==0||find(match[j]))\n\t\t\t{\n\t\t\t\tmatch[j]=x;\n\t\t\t\treturn true;\n\t\t\t}\n\t\t}\n\t}\n\treturn false;\n } \n\/\/\u6c42\u6700\u5927\u5339\u914d\u6570\uff0c\u4f9d\u6b21\u679a\u4e3e\u7b2c\u4e00\u4e2a\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u70b9\u80fd\u5426\u5339\u914d\u7b2c\u4e8c\u4e2a\u96c6\u5408\u4e2d\u7684\u70b9\nint res=0;\nfor(int i;i<=n1;i++)\/\/\u4e5f\u5c31\u662f\u6700\u5927\u5339\u914d\u6570 \n{\n\tmemset(st,false,sizeof st);\n\tif(find(i))res++;\n } <\/pre>\n","protected":false},"excerpt":{"rendered":"
dfs n\u7687\u540e \u9996\u5148\u601d\u8def\uff0c\u4f9d\u6b21\u7ed9\u6bcf\u4e00\u884c\u653e\u7687\u540e\uff0c\u5224\u65ad …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"qubely_global_settings":"","qubely_interactions":""},"categories":[1],"tags":[],"qubely_featured_image_url":null,"qubely_author":{"display_name":"ycz","author_link":"http:\/\/hiycz.cn\/index.php\/author\/ycz\/"},"qubely_comment":0,"qubely_category":"\u8003\u7814<\/a>","qubely_excerpt":"dfs n\u7687\u540e \u9996\u5148\u601d\u8def\uff0c\u4f9d\u6b21\u7ed9\u6bcf\u4e00\u884c\u653e\u7687\u540e\uff0c\u5224\u65ad …","_links":{"self":[{"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/posts\/437"}],"collection":[{"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/comments?post=437"}],"version-history":[{"count":9,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/posts\/437\/revisions"}],"predecessor-version":[{"id":461,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/posts\/437\/revisions\/461"}],"wp:attachment":[{"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/media?parent=437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/categories?post=437"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/hiycz.cn\/index.php\/wp-json\/wp\/v2\/tags?post=437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}