题解 P3084 【[USACO13OPEN]照片Photo】

从提高试炼场的dp专题蹦过来，那么显然这个题是差分约束。 （我真的不是很明白题解里的大佬怎么想到的dp，这道题的dp思路真的太巧秒了%%%，，，） 虽然USACO~~W~~卡spfa卡的不亦乐乎，但我还是决定用**梦想spfa**水一波。 分析这道题目我们可以得到这样的关系：设D[i]为前i头奶牛中斑点奶牛的数目，我们要求的就是$max(D[n])$。每个给定的区间内有且只有一个，转换为符号语言 $D[b]-D[a-1]=1$ ① 在这个性质上进一步思考，能够发现一个很显然的性质：每只奶牛要么是斑点奶牛，要么不是，转换为符号语言： $0<=D[i]-D[i-1]<=1$。② 对①整理一下,因为**有且仅有一个斑点奶牛**那么能够得到下面两个不等式： $D[b]-D[a-1]<=1,D[a-1]-D[b]<=-1$ 这样用不等式表示出它的等于性质 ②又能**写出** ：$D[i-1]-D[i]<=0$ 那么差分约束的解法就相当自然了，把i和i-1之间连一条0边，i-1和i之间连一条1边，a-1和b之间连一条1边，b和a-1之间连一条-1边，跑一手华丽的spfa，然后去研究这个题的正解dp。 那么下一个摆在你面前的问题就是如何跑一手华丽的spfa，这里我们引出梦想spfa。~~值得一提的是，只单纯的用双端队列优化的spfa正儿八经的判负环就能得到90分的好成绩。~~ ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<deque> #define Endl endl;//qwq using namespace std; const int maxn=1e6; int n,m,cnt=1; int head[maxn],vis[maxn],dis[maxn]; struct node { int nxt; int to; int w; }edge[maxn]; void add(int x,int y,int z) { edge[cnt].to=y;edge[cnt].w=z;edge[cnt].nxt=head[x];head[x]=cnt++; } //int cn[maxn]; int l,r; int tot=0; int spfa() { deque<int> q;//双端队列优化spfa memset(dis,0x3f,sizeof(dis)); dis[0]=0;//从0开始的原因见下面 vis[0]=1; q.push_back(0); while(q.size()) { int x=q.front(); q.pop_front(); vis[x]=0; for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to,z=edge[i].w; if(dis[y]>dis[x]+z) { dis[y]=dis[x]+z; //cn[y]=cn[x]+1; if(!vis[y]) { if(++tot>1926817) return -1;//人要有点信仰，这是梦想spfa的核心部分 //if(cn[y]>n)return -1;这是正儿八经的判负环，请一定要学会 vis[y]=1; if(q.size()&&dis[y]>dis[q.front()])q.push_back(y); else q.push_front(y); } } } } return dis[n]; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>l>>r; add(l-1,r,1); add(r,l-1,-1); } for(int i=1;i<=n;i++) add(i,i-1,0),add(i-1,i,1);//i-1可能为0，所以上面最短路要从0开始跑（前后呼应~~手动滑稽） cout<<spfa()<<Endl; return 0; } ```