链接:

题意:

Do not sincere non-interference。

Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once.

So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?

思路:

先找出最短路,然后将最短路的每条边加入网络流的图,边权为1,跑最大流即可.

(找最短路SPFAwa了好几次,改成Dij就过了..玄学)(SPFA写错了,真的丢人)

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 1e3+10;

const int INF = 1e9;

struct Edge

{

    int from, to, cap;

};

struct Road

{

    int from, to, len;

};

struct Dj

{

    int to, dis;

    bool operator < (const Dj &that) const

    {

        return this->dis > that.dis;

    }

};

vector<int> G[MAXN];

vector<int> GR[MAXN];

vector<int> GR2[MAXN];

vector<Edge> edges;

vector<Road> roads;

vector<Road> roads2;

int Dis[MAXN], Vis[MAXN], Dis2[MAXN];

int n, m, s, t;

void AddEdge(int from ,int to, int cap)

{

    edges.push_back(Edge{from, to, cap});

    edges.push_back(Edge{to, from, 0});

    G[from].push_back(edges.size()-2);

    G[to].push_back(edges.size()-1);

}

void Dij()

{

    memset(Vis, 0, sizeof(Vis));

    memset(Dis, MINF, sizeof(Dis));

    Dis[s] = 0;

    priority_queue<Dj> que;

    que.push(Dj{s, 0});

    while (!que.empty())

    {

        Dj u = que.top();

        que.pop();

        if (Vis[u.to])

            continue;

        Vis[u.to] = 1;

        for (int i = 0;i < GR[u.to].size();i++)

        {

            Road &r = roads[GR[u.to][i]];

            if (Dis[r.to] > Dis[u.to]+r.len)

            {

                Dis[r.to] = Dis[u.to]+r.len;

                que.push(Dj{r.to, Dis[r.to]});

            }

        }

    }

}

//void SPFA2()

//{

//    memset(Vis, 0, sizeof(Vis));

//    memset(Dis2, MINF, sizeof(Dis2));

//    Dis2[t] = 0;

//    Vis[t] = 1;

//    queue<int> que;

//    que.push(t);

//    while (!que.empty())

//    {

//        int u = que.front();

//        que.pop();

//        for (int i = 0;i < GR2[u].size();i++)

//        {

//            Road &r = roads2[GR2[u][i]];

//            if (Dis2[r.to] > Dis2[u]+r.len)

//            {

//                Dis2[r.to] = Dis2[u]+r.len;

//                if (Vis[r.to] == 0)

//                {

//                    que.push(r.to);

//                    Vis[r.to] = 1;

//                }

//            }

//        }

//    }

//}

bool Bfs()

{

    memset(Dis, -1, sizeof(Dis));

    queue<int> que;

    Dis[s] = 0;

    que.push(s);

    while (!que.empty())

    {

        int u = que.front();

        que.pop();

        for (int i = 0;i < G[u].size();i++)

        {

            Edge &e = edges[G[u][i]];

            if (e.cap > 0 && Dis[e.to] == -1)

            {

                Dis[e.to] = Dis[u]+1;

                que.push(e.to);

            }

        }

    }

    return Dis[t] != -1;

}

int Dfs(int u, int flow)

{

    if (u == t)

        return flow;

    int res = 0;

    for (int i = 0;i < G[u].size();i++)

    {

        Edge &e = edges[G[u][i]];

        if (e.cap > 0 && Dis[e.to] == Dis[u]+1)

        {

            int tmp = Dfs(e.to, min(e.cap, flow));

            flow -= tmp;

            e.cap -= tmp;

            res += tmp;

            edges[G[u][i]^1].cap += tmp;

            if (flow == 0)

                break;

        }

    }

    if (res == 0)

        Dis[u] = -1;

    return res;

}

int MaxFlow()

{

    int res = 0;

    while (Bfs())

        res += Dfs(s, INF);

    return res;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int T;

    cin >> T;

    while (T--)

    {

        cin >> n >> m;

        for (int i = 1;i <= n;i++)

            G[i].clear(), GR[i].clear();

        edges.clear(), roads.clear();

        int u, v, w;

        for (int i = 1;i <= m;i++)

        {

            cin >> u >> v >> w;

            roads.push_back(Road{u, v, w});

            GR[u].push_back(roads.size()-1);

//            roads2.push_back(Road{v, u, w});

//            GR2[v].push_back(roads2.size()-1);

        }

        cin >> s >> t;

        Dij();

//        SPFA2();

        if (Dis[t] == MINF)

        {

            cout << 0 << endl;

            continue;

        }

//        cout << 1 << endl;

        for (int i = 1;i <= n;i++)

        {

            for (int j = 0;j < GR[i].size();j++)

            {

                Road &r = roads[GR[i][j]];

//                cout << Dis[r.from] << ' ' << Dis[r.to] << ' ' << r.len << endl;

                if (Dis[r.from]+r.len == Dis[r.to])

                {

//                    cout << r.from << ' ' << r.to << endl;

                    AddEdge(r.from, r.to, 1);

                }

            }

        }

        int res = MaxFlow();

        cout << res << endl;

    }

    return 0;

}

巴特西

HDU-3416-MarriageMatch4(最大流,最短路)

链接:

题意:

思路:

代码:

最新文章

热门文章