头像

qgc123




离线:5小时前


最近来访(7)
用户头像
Beautiful_9
用户头像
Chase_future
用户头像
hey11
用户头像
阿白_08
用户头像
帝宝单推人
用户头像
咚咚
用户头像


qgc123
5小时前
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
unordered_map<int, vector<int>> mp;
const int N = 200005;
int st[N];
int res[N];
int func(int u)
{
    st[u] = 1;
    for(auto i : mp [u])
    {
        if (!st[i])
        {
            st[i] = 1;
            if (res[i] == 0 || func(res[i]))
            {
                res[i] = u;
                return 1;
            }
        }
    }
    return 0;
}


int main()
{ 
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
    }
    int ans = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof st);
            ans+=func(i);
    }
    cout << ans;
}



qgc123
5小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n,m,k;
struct ed
{
    int a, b, c;
}edge[M];
int d[N], la[N];

void bellman_ford(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 0; i < k;i++){
        memcpy(la, d, sizeof(d));
        for (int j = 0; j < m;j++){
            auto e= edge[j];
            d[e.b] = min(d[e.b], la[e.a] + e.c);
        }
    }
}
int main(){
    cin >> n >> m >> k;
    for(int i=0;i<m;i++){
        int a, b, c;
        cin >> a >> b >> c;

        edge[i] = {a, b, c};
    }
    bellman_ford();
    if(d[n]>0x3f3f3f3f/2)
        cout << "impossible" << endl;
        else{
            cout << d[n] << endl;
        }
        return 0;
}



qgc123
5小时前
#include<bits/stdc++.h>
using namespace std;
unordered_map<int, vector<int>> mp;
void add(int a, int b)
{
    mp[a].push_back(b);
}
const int N = 100005;
int st[N];
int n, m;
int p[N];
int find(int x)
{
    if (x != p[x]) return p[x] = find(p[x]);
    return p[x];
}
int bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        int u = find(i);
        if (!st[u])
        {
            q.push(u);
            st[u] = 1;
        }
    }
    while (!q.empty())
    {
        int temp = q.front();
        q.pop();
        for (int i : mp[temp])
        {
            if (st[i] == st[temp])
            {
                return 0;
            }
            else if (st[i] == 0)
            {
                q.push(i);
                st[i] = st[temp] * -1;
            }
        }
    }
        return 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        //if (a == b)continue;
        add(a, b);
        add(b, a);
        if (find(a) != find(b))
            p[find(a)] = find(b);
    }
    if (bfs() == 0)cout << "No" << endl;
    else cout << "Yes" << endl;
}



qgc123
6小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int p[N];
int n, m;
int ans;
struct edge
{
    int a, b, c;
    bool operator < (const edge &a)const
    {
        return c < a.c;
    }
}e[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];

}

int Kruskal()
{
    int cnt=0;
    for (int i = 0; i < m; i++)
    {
        int a = e[i].a, b = e[i].b, c = e[i].c;
        if (find(a) != find(b))
        {
            cnt++;
            ans += c;
            p[find(a)] = find(b);
        }
    }
    if (cnt >= n - 1) return ans;
    else return 0x3f3f3f3f;

}

int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = { a,b,c };
    }
    sort(e, e + m);

    if (Kruskal() == 0x3f3f3f3f)cout << "impossible";
    else cout << ans;

}



qgc123
6小时前
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int g[N][N];
int dis[N];
bool st[N];
int ans=0;
    int n,m;
void prim()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dis[t]>dis[j]))
            t=j;
        }
        st[t]=1;
        if(i&&dis[t]==0x3f3f3f3f) {ans=0x3f3f3f3f;return;}
        if(i); ans+=dis[t];
        for(int j=1;j<=n;j++)
        {
            if(dis[j]>g[t][j])
            {
                dis[j]=g[t][j];
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++)
    g[i][i]=0;


    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    prim();
    if(ans==0x3f3f3f3f) cout<<"impossible";
    else cout<<ans;


}



qgc123
6小时前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, q;
const int N = 250;
int g[N][N];

void floyd()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
            {
                if (g[j][k] > g[j][i] + g[i][k])
                {
                    g[j][k] = g[j][i] + g[i][k];
                }
            }
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                g[i][j] = 0;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }

    floyd();
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;
        if (g[a][b] > 0x3f3f3f3f / 2)cout << "impossible" << endl;
        else cout << g[a][b] << endl;
    }

}



qgc123
6小时前
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100005;
int e[N], ne[N], h[N], idx;
int w[N];
bool st[N];
int dis[N];
int cnt[N];
bool ans;
void add(int a, int b, int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i); 
    }
    while (q.size())
    {
        int temp = q.front();
        q.pop();
        for (int i = h[temp]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[temp] + w[i])
            {
                dis[j] = dis[temp] + w[i];
                    q.push(j);

                cnt[j]=cnt[temp]+1;
                if(cnt[j]>=n) {ans=1;return;}
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    if(ans==1) cout<<"Yes";
    else cout<<"No";
}



qgc123
6小时前
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=1e5+10;

#define fi first
#define se second

typedef pair<int,int> PII;

int h[N],e[N],w[N],ne[N],idx=0;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int spfa(){
    queue<PII> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push({0,1});
    st[1]=true;
    while(q.size()){
        PII p=q.front();
        q.pop();
        int t=p.se;
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q.push({dist[j],j});
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int res=spfa();
    if(res==-1) puts("impossible");
    else printf("%d",res);

    return 0;
}




qgc123
10小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];//
typedef pair<int, int> PII;
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII,vector<PII>, greater<PII>>heap;
    dist[1] = 0;
    heap.push({0,1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
        if(st[ver])continue;
        st[ver] = 1;
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)return -1;
    return dist[n];
}
int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = dijkstra();
    if(t == 0x3f3f3f3f)printf("-1");
    else printf("%d", t);
}





qgc123
5天前
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, g[N][N], dist[N];//dist距离 g[N][N]邻接矩阵
bool st[N];
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;

        for(int j = 1; j <= n; j++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    if(dist[n] == 0x3f3f3f3f)return -1;
    else return dist[n];
}
int main(){
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra() << endl;
    return 0;
}