bzoj 3931:[CQOI 2015]ネットワークスループット

タイトルの説明
ルーティングとは、コンピュータネットワークを介してソースアドレスから目的アドレスに情報を転送する活動であり、コンピュータネットワーク設計における重点と難点でもある.ネットワークでの実装
ルーティング転送されるハードウェアデバイスをルータと呼ぶ.パケットが最も速く目的地に到達するために、ルータは、パケットを転送するために最適なパスを選択する必要がある.たとえば、
一般的なルーティングアルゴリズムOSPF(オープン最短パス優先)では、ルータは古典的なDijkstraアルゴリズムを使用して最短パスを計算し、できるだけ最短パスに沿って計算します.
パス転送パケット.
現在、1つのコンピュータネットワークにおける各ルータ間の接続状況と、各ルータの最大スループット(すなわち、毎秒転送可能なパケット数)が既知である
量)は,すべてのパケットが必ず最短経路で転送されると仮定し,ルータ1からルータnへのネットワークの最大スループットを計算してみる.計算中に転送および転送を無視
送信される時間オーバーヘッドは、リンクの帯域幅制限を考慮せず、すなわち、パケットが瞬時にネットワークを通過できると考えられる.ルータ1からルータnまでを起点と終点とし、自身
のスループットは考慮されず,ネットワーク上にも1とnを直接接続するリンクは存在しない.
入力フォーマット
入力ファイルの最初の行には、ルータの数とリンクの数を表す2つのスペースで区切られた正の整数nとmが含まれます.ネットワーク内のルータは1からnを使用する
番号.
次に、m行は、各行に3つのスペースで区切られた正の整数a、b、dを含み、ルータaからルータbまでの距離dの双方向リンクがあることを示す.
次にn行、各行は正の整数cを含み、各ルータのスループットをそれぞれ与える.
出力フォーマット
整数を出力し、問題のスループットを求めます.
入力サンプル
7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
11
00
20
50
20
60
1
出力サンプル
70
データ範囲
30%のデータに対してn≦100,m≦1000
100%のデータに対してn≦500,m≦100000,d,c≦10^9
タイトルフォーマットはこうしましょう....
裸の最大流.まず最短図を飛び出します.次に、制限流量を分解して最大流を走ればいいです.
longlongを運転してください.最初はわけがわからなくてT

#include
#include
#include
#include
using namespace std;
inline int min(int x,int y)
{
     if(x0&&d[a[i].t]==-1)
               {
                    d[a[i].t]=d[k]+1;
                    r++;
                    q[r]=a[i].t;
               }
          }
     }
     if(d[p]>=0)
          return true;
     return false;
}
inline long long dfs(int k,long long s)
{
     if(k==p)
          return s;
     long long t=s;
     int i;
     for(i=head[k];i!=0;i=a[i].next)
     {
          if(d[a[i].t]==d[k]+1&&a[i].f>0)
          {
               long long xx=dfs(a[i].t,min(s,a[i].f));
               a[i].f-=xx;
               if(i%2==0)
                    a[i-1].f+=xx;
               else
                    a[i+1].f+=xx;
               s-=xx;
          }
     }
     return t-s;
}
inline long long maxflow()
{
     long long s=0;
     while(bfs())
          s+=dfs(1,(long long)1000000000*(long long)5000);
     return s;
}
long long dis[501];
bool v[501];
inline void spfa()
{
	 int i;
	 for(i=1;i<=500;i++)
	      dis[i]=(long long)1000000000*(long long)5000;
	 memset(v,false,sizeof(v));
     queue Q;
     while(!Q.empty())
          Q.pop();
     Q.push(1);
     dis[1]=0;
     v[1]=true;
     while(!Q.empty())
     {
          int d=Q.front();
          v[d]=false;
          Q.pop();
          int i;
          for(i=exhead[d];i!=0;i=exa[i].next)
          {
               int t=exa[i].t;
               if(dis[d]+exa[i].f