2019.07.11【NOIP提高組】模拟 A 組（求上、下凸殼）

T1：簡單的線段樹維護。

T2：這題正解很簡單，幾乎所有人都想出來了，但是我想了很久都沒思路。

一開始我以為是一個網絡流，想了一會發現不會建圖。

比賽結束後發現其實就是一個最小生成樹。因為我們要把圖連成許多個聯通塊，每一個聯通塊都要有一個被選中的點，那麼我們就建立一個節點，這個節點向其他點連邊的邊權就是選中那個點的代價。建好新點之後，直接做最小生成樹就可以了。

總結：以後遇到這種花最小代價使圖聯通的題目就要往最小生成樹方向想。因為最小生成樹的定義就是這個。

T3：首先利用經過x的個數進行分層SPFA。完了之後我們發現所有可能的最短路都可以表示成kx+b的形式。

那麼這題就轉化成了有許多條直線，我們要求x在一個範圍内的最小值的個數和最小值的和。

再分析一下發現題目要求的就是一個上凸殼。上凸殼的求法：先按k從小到大（從大到小也行，隻要是有序的就可以了）排序，然後如果之前兩條直線的交點在目前直線的左邊，那麼就彈棧。

（拓展：求下凸殼。先按k排序，然後加邊，不過這次是交點在右邊才彈棧。）

最後求答案時要用等差數列求和，不能枚舉x（因為x會很大）。

細節較多，貼一下代碼：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define db long double
#define MAXN 510
#define MAXM 10010
using namespace std;

struct map
{
	ll x;
	ll y;
	ll l;
	ll k;
};
map way[MAXM];
struct dot
{
	db px;
	db py;
	db vx;
	db vy;
};
dot c[MAXN];
ll first[MAXN],next[MAXM],dis[MAXN][MAXN],bz[MAXN][MAXN],d[MAXN*MAXN*5][2],n,m,T,sd,td,ans1,ans2;
ll inf,t,g[MAXN],s,lim;
db x,y;
int SPFA()
{
	ll i,j,h,t;
	memset(dis,0x7f,sizeof(dis));inf=dis[0][0];
	memset(bz,0,sizeof(bz));
	dis[sd][0]=0;bz[sd][0]=1;
	d[1][0]=sd;d[1][1]=0;
	h=0;t=1;
	while(h<t)
	{
		h++;
		i=first[d[h][0]];
		while(i>=1&&i<=m)
		{
			if(way[i].k==0)
			{
				if(dis[d[h][0]][d[h][1]]+way[i].l<dis[way[i].y][d[h][1]])
				{
					dis[way[i].y][d[h][1]]=dis[d[h][0]][d[h][1]]+way[i].l;
					if(bz[way[i].y][d[h][1]]==0)
					{
						t++;d[t][0]=way[i].y;d[t][1]=d[h][1];
						bz[d[t][0]][d[t][1]]=1;
					}
				}
			}
			else
				if(d[h][1]<lim)
					if(dis[d[h][0]][d[h][1]]<dis[way[i].y][d[h][1]+1])
					{
						dis[way[i].y][d[h][1]+1]=dis[d[h][0]][d[h][1]];
						if(bz[way[i].y][d[h][1]+1]==0)
						{
							t++;d[t][0]=way[i].y;d[t][1]=d[h][1]+1;
							bz[d[t][0]][d[t][1]]=1;
						}
					}
			i=next[i];
		}
		bz[d[h][0]][d[h][1]]=0;
	}
}
ll read()
{
	ll s=0;
	char x=getchar();
	while(x<'0'||x>'9')
	{
		if(x=='x')return -1;
		x=getchar();
	}
	while('0'<=x&&x<='9')s=s*10+x-'0',x=getchar();
	return s;
}
db cro(db x1,db y1,db x2,db y2){return x1*y2-x2*y1;}
db inter(ll i,ll j)
{
	db c1,c2,g;
	c1=cro(c[i].vx,c[i].vy,c[i].px-c[j].px,c[i].py-c[j].py);
	c2=cro(c[i].vx,c[i].vy,c[j].vx,c[j].vy);
	g=c1/c2;
	x=c[j].px+c[j].vx*g;
	y=c[j].py+c[j].vy*g;
}
db val(db x,ll i){return c[i].py+(x-c[i].px)*c[i].vy;}
ll up(db x)
{
	if(x==(ll)x)return x;
	else return (ll)x+1;
}
ll down(db x){return (ll)x;}
int main()
{
ll i,j,tim,tf;
db lx,ly;
n=read();m=read();
for(i=1;i<=m;i++)
{
	way[i].x=read();way[i].y=read();way[i].l=read();
}
for(i=1;i<=m;i++)
	if(way[i].l==-1)way[i].k=1;
for(i=m;i>=1;i--)next[i]=first[way[i].x],first[way[i].x]=i;
if(n>m)lim=m;
else lim=n;
scanf("%lld",&T);
while(T>=1)
{
	scanf("%lld %lld\n",&sd,&td);
	SPFA();
	tf=0;
	for(i=0;i<=lim;i++)
		if(dis[td][i]!=inf){tf=1;break;}
	if(tf==0){printf("0 0\n");T--;continue;}
	if(dis[td][0]==inf){printf("inf\n");T--;continue;}
	s=0;
	for(i=0;i<=lim;i++)
	{
		if(dis[td][i]==inf)continue;
		s++;
		c[s].px=0;c[s].py=dis[td][i];
		c[s].vx=1;c[s].vy=i;
	}
	t=0;
	for(i=1;i<=s;i++)
	{
		while(t>1)
		{
			inter(g[t],g[t-1]);
			if(cro(c[i].vx,c[i].vy,x-c[i].px,y-c[i].py)>0)t--;
			else break;
		}
		t++;g[t]=i;
	}
	ans1=0;ans2=0;
	lx=1;tim=0;
	for(i=t-1;i>=1;i--)
	{
		inter(g[i+1],g[i]);
		if(up(lx)>down(x))continue;
		tim++;
		ans1=ans1+down(x)-up(lx)+1;
		ans2=ans2+(val(up(lx),g[i+1])+val(down(x),g[i+1]))*(down(x)-up(lx)+1)/2;
		if(tim!=1&&up(lx)==lx){ans1--;ans2-=val(up(lx),g[i+1]);}
		lx=x;
	}
	if(val(down(x),g[2])!=c[g[1]].py){ans1++;ans2=ans2+c[g[1]].py;}
	printf("%lld %lld\n",ans1,ans2);
	T--;
}
}