依赖01背包+差分约束

P1260 工程规划

引入超级源点，得到每个任务最大能满足的要求 用各个任务减去这个最小值，就是各个工程开始的时间。

无解的情况：spfa中每个点别松弛n-1次，如果有点被松弛了n次，则无解。

#include 
#define int long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,head[maxn],cnt,dist[maxn],num[maxn];
bool vis[maxn];
struct node
{
    int to,nxt,dis;
}e[maxn];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
queueq;
bool spfa(int u)
{
    memset(dist,inf,sizeof(dist));
    dist[u]=0;
    q.push(u);
    vis[u]=1;
    num[u]++;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].dis)
            {
                dist[v]=dist[u]+e[i].dis;
                if(!vis[v])
                {
                    num[v]++;
                    q.push(v);
                    vis[v]=1;
                    if(num[v]==n)
                        return 0;
                }
            }
        }
    }
    return 1;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i