题目链接

题面：

题意：
给定n，有一个 [ 1 , n ] 数对。
现在对于任意一个数对 [ l , r ] ，如果l<r，那么他可以进行如下变化。
① 变到 [ l + 1 , r ] 或 者 [ l , r - 1 ]
② 变到 [ l - 1 , r ] ( l > 1 ) 或 者 [ l ,r + 1 ] ( r < n )
如果 l = r 那么就不能再操作了。
给定一些限制条件，l，r，dir，c
如果 dir = L，那么我可以花费 c 阻止 [ l , r ] 变到[ l + 1 , r ]
如果 dir = R，那么我可以花费 c 阻止 [ l , r ] 变到[ l , r - 1 ]

我不想 [ 1 , n ] ，变到 [ l , r ] 其中 l = r。
问我最少花费多少才能阻止，或者说我不能阻止，输出-1。

官方题解：

题解：
我们使得每一个（l，r）作为一个顶点，源点为（1，n）。
初始时，所有边的权值为无穷大。
如果花费 c 能阻止 [ l , r ] 变到[ l + 1 , r ]，那么就让[ l , r ] 到[ l + 1 , r ]的边的权值为c
如果花费 c 能阻止 [ l , r ] 变到[ l , r - 1 ]，那么也让 [ l , r ] 到[ l , r - 1 ]的边的权值为c

其实我们只用了这个网格图的右上半部分，所有的（ i，i ）都是汇点。
我们可以设一个超级汇点，所有的 ( i , i ) 向这个汇点连一条无穷大的边。

这样，我们只需要求出这个图的最小割（最大流）即可。

考虑将这个平面图转化为对偶图，将平面图的最大流变为对偶图的最短路。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=500100;
const int maxm=100100;
const int up=1000;

int head[maxn],ver[maxn],edge[maxn],nt[maxn],tot=1,s,t;
ll d[maxn];
bool ha[maxn];

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=z,nt[tot]=head[y],head[y]=tot;
}

ll dij(void)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<pair<ll,int> >q;
    q.push(pr(0,s));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(pr(-d[y],y));
            }
        }
    }
    return d[t];
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    int l,r,c;
    char str[10];
    s=(n-1)*(n-1)+1;
    t=s+1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%s%d",&l,&r,str,&c);
        if(str[0]=='L')
        {
            if(r==n) add(l*(n-1),t,c);
            else add((l-1)*(n-1)+r-1,(l-1)*(n-1)+r,c);
        }
        else
        {
            if(l==1) add(r-1,s,c);
            else add((l-2)*(n-1)+r-1,(l-1)*(n-1)+r-1,c);
        }
    }
    ll ans=dij();
    printf("%lld\n",ans==lnf?-1:ans);
    return 0;
}