41 条题解
-
20
xzp LV 6 @ 2017-06-10 14:28:46
由于题中给出的是一个完全图的最小生成树的树边，对于题中给出每一条边（u，v），显然u和v并不连通。因为原图为一个完全图，那么完全图的部分点构成的图也为完全图。假设u所在完全图G1中，G1中有点n1个，v所在完全图G2中，G2中有点n2个，那么，连接边（u，v），并且使得u，v两个完全图合为一个完全图还需要连n1*n2-1条边，边权至少要大于边（u，v）的权值，要让完全图边权总和最小，即让这n1*n2-1条边的边权为边（u，v）的边权加1即可。
但我们又想到一个问题，怎么保证这样生成的完全图的最小生成树和原题相同？显然，先连接边权大的边，在连接边权小的边，前面连接的边权较大的边会被后面边权小的边连接时补全图为完全图时的边替代。文字难以理解，这里讲一个简单的例子。
3
2 3 7
1 2 4
没错，就是样例，只是将第一条边和第二条边的位置互换，处理时我们从前往后处理。第一条边权值为7，连接后不需要补边（已经为完全图），第二条边权值为4，需要补边（1,3）才能使原图变为完全图，权值为当前边权值加1，即为5，显然，在最小生成树中，边（2,3）会被边（1,3）替代，即操作不合法。
但是，如果我们保证前面的边的边权小于等于后面的边权，那么，求出的完全图的正确性就有保障了。
根据上面所讲，这题和kruskal是不是很像？一开始将边以边权从小到大排序，记录每个点所在集合中的元素个数为d[i]，对于每一条边（u，v），边权为val，ans+=val+（val+1）*（d[root[u]]*d[root[v]]-1）其中root[i]表示i所在集合的代表元素。最后输出ans即可。#include<cstdio> #include<algorithm> using namespace std; struct node { int x,y,z; }edge[20005]; int n,fa[20005]; long long ans,d[20005]; bool cmp(node a,node b) { if (a.z<b.z) return true; else return false; } int find(int x) { if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } int main() { scanf("%d",&n); for (int i=1; i<n; i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z); sort(edge+1,edge+n,cmp); for (int i=1; i<=n; i++) { fa[i]=i; d[i]=1; } for (int i=1; i<n; i++) { int rx=find(edge[i].x); int ry=find(edge[i].y); ans+=edge[i].z+(edge[i].z+1)*(d[rx]*d[ry]-1); d[ry]+=d[rx]; fa[rx]=ry; } printf("%lld\n",ans); return 0; } -
3
并查集+最小生成树的逆过程
边的权重一定要unsigned long long，反正我int是2次没过了。
把边按权重从小到大排，算该边链接的两个连通分量的节点数，之后如果把两个完全连通图补成一个完全连通图，需要加an * bn条边，其中有一条边是最小生成树上的边了，另外其他边都要求比它的权重大，所以每次都加(an * bn-1) * (w+1).#include <iostream> #include <algorithm> using namespace std; typedef struct { int a=0,b=0; unsigned long long w=0; }edge; int n; edge e[20005]; int f[20005]; int num[20005]; int fi(int x) { if(f[x]==x) { return x; } return f[x]=fi(f[x]); } void un(int a,int b) { int x=fi(a); int y=fi(b); if(x!=y) { f[y]=x; num[x]+=num[y]; } } bool comp(edge a,edge b) { return a.w<b.w; } int main() { cin>>n; int i; unsigned long long ans=0; for(i=0;i<=n;i++) { f[i]=i; num[i]=1; } for(i=0;i<n-1;i++) { cin>>e[i].a>>e[i].b>>e[i].w; ans+=e[i].w; } sort(e,e+n-1,comp); int na,nb; for(i=0;i<n-1;i++) { na=num[fi(e[i].a)]; nb=num[fi(e[i].b)]; ans+=(na*nb-1)*(e[i].w+1); un(e[i].a,e[i].b); } cout<<ans<<endl; return 0; } -
2
一个逆向做最小生成树的过程,考虑Kruskal的实现过程,一条沟通两个联通块的边且后面的边都比当前边大.所以对于给出的树边实际上都沟通了两个不同的联通的块且边权为其他所有连接两个联通块中最小值.
那么其他边实际上有(size[x]*size[y])-1 那么多 而权值为当前值+1#include<bits/stdc++.h> using namespace std; const int N=20000+10; typedef long long ll; struct Edge { int from,to,val; bool operator <(const Edge& rhs)const { return rhs.val>val; } }e[N]; int last[N],fa[N],s[N]; int n;ll ans; int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);} void Kruskal() { for(int i=1;i<n;i++) { int idx=find(e[i].from),idy=find(e[i].to); ans+=(ll(s[idx])*ll(s[idy])-1)*(e[i].val+1); s[idy]+=s[idx]; fa[idx]=idy; } printf("%lld\n",ans); } int main() { scanf("%d",&n); for(int u,v,w,i=1;i<n;i++) { fa[i]=i;s[i]=1; scanf("%d%d%d",&u,&v,&w); ans+=w; e[i].from=u;e[i].to=v;e[i].val=w; }fa[n]=n;s[n]=1; sort(e+1,e+n); Kruskal(); return 0; } -
0
想了很久，尝试寻找两点间原边的最大值，但处理后需要n2模拟，果断放弃。
之后想将点用原边最大值排序，发现无法处理相邻边的情况，果断放弃。无奈，只好翻题解。
写完发现，实际上这两个方法思想上差不多，但逆用kruskal完美处理了点间相连的情况（最小被最大覆盖，于是先用小边连接集合。然后单边的连接有巧妙解决了相邻边的情况。siz的记录更让统计变得快当有力。）
可惜，虽然没有想出正解，但长时间沉浸于思考给我带来的快乐实在是。。。
#include<algorithm> #include<iostream> #define LL long long using namespace std; struct EDGE { LL u,v,dis; }; LL n; LL fa[20010],siz[20010]; EDGE eset[20010]; bool cmp (EDGE pa,EDGE pb) { return pa.dis<pb.dis; } int find (int p) { return fa[p]==p?p:fa[p]=find(fa[p]); } void uin (LL pa,LL pb) { LL fapa=find(pa),fapb=find(pb); if (fapa==fapb) return; fa[fapb]=fapa; siz[fapa]+=siz[fapb],siz[fapb]=0; } int main () { ios::sync_with_stdio(false); LL ans=0; cin>>n; for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; for(int i=1;i<n;i++) { int u,v,dis; cin>>u>>v>>dis; ans+=dis; eset[i]=(EDGE){u,v,dis}; } sort(eset+1,eset+n,cmp); for(int i=1;i<n;i++) { LL pa=eset[i].u,pb=eset[i].v,dis=eset[i].dis; LL fapa=find(pa),fapb=find(pb); ans+=(siz[fapa]*siz[fapb]-1)*(dis+1); uin(pa,pb); } cout<<ans<<endl; return 0; } -
-2
wang_yanheng LV 10 @ 2016-08-03 16:57:55
好题目，一开始想简单了，最后发现还是得用并查集。
参照 Kruskal 的思路：
先对边表进行排序，然后依次枚举边。依据 MST 的定义及 kruskal 的流程知，**当前边 E[i] 的两个顶点 u 和 v 一定分属不同的集合**。设这两个集合大小分别为size[u]和size[v]。那么两集合之间除了 E[i] 之外可以再连接size[u]*size[v]-1条边。很显然这些边的权值最小为 E[i] 的权值+1。所以ans += (size[u]*size[v]-1)*(E[i].w+1)。枚举完即构成完全图。输出 ans 即可。
至于 size 怎么得到，在并查集合并时加一句话就行了。
提醒：中间结果要用 long long / int64。 -
-2
for i:=1 to n-1 do
begin
now:=max(big[getfa(x[i])],big[getfa(y[i])]);
a:=num[getfa(x[i])]; b:=num[getfa(y[i])];
union(x[i],y[i]); mark:=getfa(x[i]);
num[mark]:=a+b+1;
big[mark]:=max(now,len[i]);
inc(ans,(big[mark]+1)*leave+len[i]);
end;
writeln(ans);
end.
{
逆向KURSKAL 注意都是INT64啊
} -
-2
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms并查集哦哦！
-
-2
我的题一般都有毛病，大家海涵！
出题者解题报告+AC代码：http://xujieqi.blog.hexun.com/36115230_d.html -
-2
hhdllhflower LV 10 @ 2009-07-18 18:12:28
╮(╯▽╰)╭
晚了 -
-3
//铁一中二楼机房欢迎您！ #ifndef _GLIBCXX_IOSTREAM #define _GLIBCXX_IOSTREAM 1 #pragma GCC system_header #include <bits/c++config.h> #ifndef _GLIBCXX_OSTREAM #define _GLIBCXX_OSTREAM 1 #pragma GCC system_header #ifndef _GLIBCXX_IOS #define _GLIBCXX_IOS 1 #pragma GCC system_header #ifndef _GLIBCXX_IOSFWD #define _GLIBCXX_IOSFWD 1 #pragma GCC system_header #include <bits/c++config.h> #include <bits/stringfwd.h> // For string forward declarations. #include <bits/postypes.h> namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * @defgroup io I/O * * Nearly all of the I/O classes are parameterized on the type of * characters they read and write. (The major exception is ios_base at * the top of the hierarchy.) This is a change from pre-Standard * streams, which were not templates. * * For ease of use and compatibility, all of the basic_* I/O-related * classes are given typedef names for both of the builtin character * widths (wide and narrow). The typedefs are the same as the * pre-Standard names, for example: * * @code * typedef basic_ifstream<char> ifstream; * @endcode * * Because properly forward-declaring these classes can be difficult, you * should not do it yourself. Instead, include the <iosfwd> * header, which contains only declarations of all the I/O classes as * well as the typedefs. Trying to forward-declare the typedefs * themselves (e.g., <code>class ostream;</code>) is not valid ISO C++. * * For more specific declarations, see * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt11ch24.html * * @{ */ class ios_base; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_ios; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_streambuf; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_istream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_ostream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_iostream; template<typename _CharT, typename _Traits = char_traits<_CharT>, typename _Alloc = allocator<_CharT> > class basic_stringbuf; template<typename _CharT, typename _Traits = char_traits<_CharT>, typename _Alloc = allocator<_CharT> > class basic_istringstream; template<typename _CharT, typename _Traits = char_traits<_CharT>, typename _Alloc = allocator<_CharT> > class basic_ostringstream; template<typename _CharT, typename _Traits = char_traits<_CharT>, typename _Alloc = allocator<_CharT> > class basic_stringstream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_filebuf; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_ifstream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_ofstream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class basic_fstream; template<typename _CharT, typename _Traits = char_traits<_CharT> > class istreambuf_iterator; template<typename _CharT, typename _Traits = char_traits<_CharT> > class ostreambuf_iterator; /// Base class for @c char streams. typedef basic_ios<char> ios; /// Base class for @c char buffers. typedef basic_streambuf<char> streambuf; /// Base class for @c char input streams. typedef basic_istream<char> istream; /// Base class for @c char output streams. typedef basic_ostream<char> ostream; /// Base class for @c char mixed input and output streams. typedef basic_iostream<char> iostream; /// Class for @c char memory buffers. typedef basic_stringbuf<char> stringbuf; /// Class for @c char input memory streams. typedef basic_istringstream<char> istringstream; /// Class for @c char output memory streams. typedef basic_ostringstream<char> ostringstream; /// Class for @c char mixed input and output memory streams. typedef basic_stringstream<char> stringstream; /// Class for @c char file buffers. typedef basic_filebuf<char> filebuf; /// Class for @c char input file streams. typedef basic_ifstream<char> ifstream; /// Class for @c char output file streams. typedef basic_ofstream<char> ofstream; /// Class for @c char mixed input and output file streams. typedef basic_fstream<char> fstream; #ifdef _GLIBCXX_USE_WCHAR_T /// Base class for @c wchar_t streams. typedef basic_ios<wchar_t> wios; /// Base class for @c wchar_t buffers. typedef basic_streambuf<wchar_t> wstreambuf; /// Base class for @c wchar_t input streams. typedef basic_istream<wchar_t> wistream; /// Base class for @c wchar_t output streams. typedef basic_ostream<wchar_t> wostream; /// Base class for @c wchar_t mixed input and output streams. typedef basic_iostream<wchar_t> wiostream; /// Class for @c wchar_t memory buffers. typedef basic_stringbuf<wchar_t> wstringbuf; /// Class for @c wchar_t input memory streams. typedef basic_istringstream<wchar_t> wistringstream; /// Class for @c wchar_t output memory streams. typedef basic_ostringstream<wchar_t> wostringstream; /// Class for @c wchar_t mixed input and output memory streams. typedef basic_stringstream<wchar_t> wstringstream; /// Class for @c wchar_t file buffers. typedef basic_filebuf<wchar_t> wfilebuf; /// Class for @c wchar_t input file streams. typedef basic_ifstream<wchar_t> wifstream; /// Class for @c wchar_t output file streams. typedef basic_ofstream<wchar_t> wofstream; /// Class for @c wchar_t mixed input and output file streams. typedef basic_fstream<wchar_t> wfstream; #endif /** @} */ _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif /* _GLIBCXX_IOSFWD */ #include <exception> // For ios_base::failure #include <bits/char_traits.h> // For char_traits, streamoff, streamsize, fpos #include <bits/localefwd.h> // For class locale #include <bits/ios_base.h> // For ios_base declarations. #include <streambuf> #include <bits/basic_ios.h> #endif /* _GLIBCXX_IOS */ #ifndef _OSTREAM_INSERT_H #define _OSTREAM_INSERT_H 1 #pragma GCC system_header #include <iosfwd> #include <bits/cxxabi_forced.h> namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _CharT, typename _Traits> inline void __ostream_write(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s, streamsize __n) { typedef basic_ostream<_CharT, _Traits> __ostream_type; typedef typename __ostream_type::ios_base __ios_base; const streamsize __put = __out.rdbuf()->sputn(__s, __n); if (__put != __n) __out.setstate(__ios_base::badbit); } template<typename _CharT, typename _Traits> inline void __ostream_fill(basic_ostream<_CharT, _Traits>& __out, streamsize __n) { typedef basic_ostream<_CharT, _Traits> __ostream_type; typedef typename __ostream_type::ios_base __ios_base; const _CharT __c = __out.fill(); for (; __n > 0; --__n) { const typename _Traits::int_type __put = __out.rdbuf()->sputc(__c); if (_Traits::eq_int_type(__put, _Traits::eof())) { __out.setstate(__ios_base::badbit); break; } } } template<typename _CharT, typename _Traits> basic_ostream<_CharT, _Traits>& __ostream_insert(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s, streamsize __n) { typedef basic_ostream<_CharT, _Traits> __ostream_type; typedef typename __ostream_type::ios_base __ios_base; typename __ostream_type::sentry __cerb(__out); if (__cerb) { __try { const streamsize __w = __out.width(); if (__w > __n) { const bool __left = ((__out.flags() & __ios_base::adjustfield) == __ios_base::left); if (!__left) __ostream_fill(__out, __w - __n); if (__out.good()) __ostream_write(__out, __s, __n); if (__left && __out.good()) __ostream_fill(__out, __w - __n); } else __ostream_write(__out, __s, __n); __out.width(0); } __catch(__cxxabiv1::__forced_unwind&) { __out._M_setstate(__ios_base::badbit); __throw_exception_again; } __catch(...) { __out._M_setstate(__ios_base::badbit); } } return __out; } // Inhibit implicit instantiations for required instantiations, // which are defined via explicit instantiations elsewhere. #if _GLIBCXX_EXTERN_TEMPLATE extern template ostream& __ostream_insert(ostream&, const char*, streamsize); #ifdef _GLIBCXX_USE_WCHAR_T extern template wostream& __ostream_insert(wostream&, const wchar_t*, streamsize); #endif #endif _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif /* _OSTREAM_INSERT_H */ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * @brief Template class basic_ostream. * @ingroup io * * @tparam _CharT Type of character stream. * @tparam _Traits Traits for character type, defaults to * char_traits<_CharT>. * * This is the base class for all output streams. It provides text * formatting of all builtin types, and communicates with any class * derived from basic_streambuf to do the actual output. */ template<typename _CharT, typename _Traits> class basic_ostream : virtual public basic_ios<_CharT, _Traits> { public: // Types (inherited from basic_ios): typedef _CharT char_type; typedef typename _Traits::int_type int_type; typedef typename _Traits::pos_type pos_type; typedef typename _Traits::off_type off_type; typedef _Traits traits_type; // Non-standard Types: typedef basic_streambuf<_CharT, _Traits> __streambuf_type; typedef basic_ios<_CharT, _Traits> __ios_type; typedef basic_ostream<_CharT, _Traits> __ostream_type; typedef num_put<_CharT, ostreambuf_iterator<_CharT, _Traits> > __num_put_type; typedef ctype<_CharT> __ctype_type; /** * @brief Base constructor. * * This ctor is almost never called by the user directly, rather from * derived classes' initialization lists, which pass a pointer to * their own stream buffer. */ explicit basic_ostream(__streambuf_type* __sb) { this->init(__sb); } /** * @brief Base destructor. * * This does very little apart from providing a virtual base dtor. */ virtual ~basic_ostream() { } /// Safe prefix/suffix operations. class sentry; friend class sentry; //@{ /** * @brief Interface for manipulators. * * Manipulators such as @c std::endl and @c std::hex use these * functions in constructs like "std::cout << std::endl". For more * information, see the iomanip header. */ __ostream_type& operator<<(__ostream_type& (*__pf)(__ostream_type&)) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 60. What is a formatted input function? // The inserters for manipulators are *not* formatted output functions. return __pf(*this); } __ostream_type& operator<<(__ios_type& (*__pf)(__ios_type&)) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 60. What is a formatted input function? // The inserters for manipulators are *not* formatted output functions. __pf(*this); return *this; } __ostream_type& operator<<(ios_base& (*__pf) (ios_base&)) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 60. What is a formatted input function? // The inserters for manipulators are *not* formatted output functions. __pf(*this); return *this; } //@} //@{ /** * @name Inserters * * All the @c operator<< functions (aka <em>formatted output * functions</em>) have some common behavior. Each starts by * constructing a temporary object of type std::basic_ostream::sentry. * This can have several effects, concluding with the setting of a * status flag; see the sentry documentation for more. * * If the sentry status is good, the function tries to generate * whatever data is appropriate for the type of the argument. * * If an exception is thrown during insertion, ios_base::badbit * will be turned on in the stream's error state without causing an * ios_base::failure to be thrown. The original exception will then * be rethrown. */ //@{ /** * @brief Integer arithmetic inserters * @param __n A variable of builtin integral type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to perform numeric formatting. */ __ostream_type& operator<<(long __n) { return _M_insert(__n); } __ostream_type& operator<<(unsigned long __n) { return _M_insert(__n); } __ostream_type& operator<<(bool __n) { return _M_insert(__n); } __ostream_type& operator<<(short __n); __ostream_type& operator<<(unsigned short __n) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 117. basic_ostream uses nonexistent num_put member functions. return _M_insert(static_cast<unsigned long>(__n)); } __ostream_type& operator<<(int __n); __ostream_type& operator<<(unsigned int __n) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 117. basic_ostream uses nonexistent num_put member functions. return _M_insert(static_cast<unsigned long>(__n)); } #ifdef _GLIBCXX_USE_LONG_LONG __ostream_type& operator<<(long long __n) { return _M_insert(__n); } __ostream_type& operator<<(unsigned long long __n) { return _M_insert(__n); } #endif //@} //@{ /** * @brief Floating point arithmetic inserters * @param __f A variable of builtin floating point type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to perform numeric formatting. */ __ostream_type& operator<<(double __f) { return _M_insert(__f); } __ostream_type& operator<<(float __f) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 117. basic_ostream uses nonexistent num_put member functions. return _M_insert(static_cast<double>(__f)); } __ostream_type& operator<<(long double __f) { return _M_insert(__f); } //@} /** * @brief Pointer arithmetic inserters * @param __p A variable of pointer type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to perform numeric formatting. */ __ostream_type& operator<<(const void* __p) { return _M_insert(__p); } /** * @brief Extracting from another streambuf. * @param __sb A pointer to a streambuf * * This function behaves like one of the basic arithmetic extractors, * in that it also constructs a sentry object and has the same error * handling behavior. * * If @p __sb is NULL, the stream will set failbit in its error state. * * Characters are extracted from @p __sb and inserted into @c *this * until one of the following occurs: * * - the input stream reaches end-of-file, * - insertion into the output sequence fails (in this case, the * character that would have been inserted is not extracted), or * - an exception occurs while getting a character from @p __sb, which * sets failbit in the error state * * If the function inserts no characters, failbit is set. */ __ostream_type& operator<<(__streambuf_type* __sb); //@} //@{ /** * @name Unformatted Output Functions * * All the unformatted output functions have some common behavior. * Each starts by constructing a temporary object of type * std::basic_ostream::sentry. This has several effects, concluding * with the setting of a status flag; see the sentry documentation * for more. * * If the sentry status is good, the function tries to generate * whatever data is appropriate for the type of the argument. * * If an exception is thrown during insertion, ios_base::badbit * will be turned on in the stream's error state. If badbit is on in * the stream's exceptions mask, the exception will be rethrown * without completing its actions. */ /** * @brief Simple insertion. * @param __c The character to insert. * @return *this * * Tries to insert @p __c. * * @note This function is not overloaded on signed char and * unsigned char. */ __ostream_type& put(char_type __c); /** * @brief Core write functionality, without sentry. * @param __s The array to insert. * @param __n Maximum number of characters to insert. */ void _M_write(const char_type* __s, streamsize __n) { const streamsize __put = this->rdbuf()->sputn(__s, __n); if (__put != __n) this->setstate(ios_base::badbit); } /** * @brief Character string insertion. * @param __s The array to insert. * @param __n Maximum number of characters to insert. * @return *this * * Characters are copied from @p __s and inserted into the stream until * one of the following happens: * * - @p __n characters are inserted * - inserting into the output sequence fails (in this case, badbit * will be set in the stream's error state) * * @note This function is not overloaded on signed char and * unsigned char. */ __ostream_type& write(const char_type* __s, streamsize __n); //@} /** * @brief Synchronizing the stream buffer. * @return *this * * If @c rdbuf() is a null pointer, changes nothing. * * Otherwise, calls @c rdbuf()->pubsync(), and if that returns -1, * sets badbit. */ __ostream_type& flush(); /** * @brief Getting the current write position. * @return A file position object. * * If @c fail() is not false, returns @c pos_type(-1) to indicate * failure. Otherwise returns @c rdbuf()->pubseekoff(0,cur,out). */ pos_type tellp(); /** * @brief Changing the current write position. * @param __pos A file position object. * @return *this * * If @c fail() is not true, calls @c rdbuf()->pubseekpos(pos). If * that function fails, sets failbit. */ __ostream_type& seekp(pos_type); /** * @brief Changing the current write position. * @param __off A file offset object. * @param __dir The direction in which to seek. * @return *this * * If @c fail() is not true, calls @c rdbuf()->pubseekoff(off,dir). * If that function fails, sets failbit. */ __ostream_type& seekp(off_type, ios_base::seekdir); protected: basic_ostream() { this->init(0); } template<typename _ValueT> __ostream_type& _M_insert(_ValueT __v); }; /** * @brief Performs setup work for output streams. * * Objects of this class are created before all of the standard * inserters are run. It is responsible for <em>exception-safe prefix and * suffix operations</em>. */ template <typename _CharT, typename _Traits> class basic_ostream<_CharT, _Traits>::sentry { // Data Members. bool _M_ok; basic_ostream<_CharT, _Traits>& _M_os; public: /** * @brief The constructor performs preparatory work. * @param __os The output stream to guard. * * If the stream state is good (@a __os.good() is true), then if the * stream is tied to another output stream, @c is.tie()->flush() * is called to synchronize the output sequences. * * If the stream state is still good, then the sentry state becomes * true (@a okay). */ explicit sentry(basic_ostream<_CharT, _Traits>& __os); /** * @brief Possibly flushes the stream. * * If @c ios_base::unitbuf is set in @c os.flags(), and * @c std::uncaught_exception() is true, the sentry destructor calls * @c flush() on the output stream. */ ~sentry() { // XXX MT if (bool(_M_os.flags() & ios_base::unitbuf) && !uncaught_exception()) { // Can't call flush directly or else will get into recursive lock. if (_M_os.rdbuf() && _M_os.rdbuf()->pubsync() == -1) _M_os.setstate(ios_base::badbit); } } /** * @brief Quick status checking. * @return The sentry state. * * For ease of use, sentries may be converted to booleans. The * return value is that of the sentry state (true == okay). */ #if __cplusplus >= 201103L explicit #endif operator bool() const { return _M_ok; } }; //@{ /** * @brief Character inserters * @param __out An output stream. * @param __c A character. * @return out * * Behaves like one of the formatted arithmetic inserters described in * std::basic_ostream. After constructing a sentry object with good * status, this function inserts a single character and any required * padding (as determined by [22.2.2.2.2]). @c __out.width(0) is then * called. * * If @p __c is of type @c char and the character type of the stream is not * @c char, the character is widened before insertion. */ template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __out, _CharT __c) { return __ostream_insert(__out, &__c, 1); } template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __out, char __c) { return (__out << __out.widen(__c)); } // Specialization template <class _Traits> inline basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& __out, char __c) { return __ostream_insert(__out, &__c, 1); } // Signed and unsigned template<class _Traits> inline basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& __out, signed char __c) { return (__out << static_cast<char>(__c)); } template<class _Traits> inline basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c) { return (__out << static_cast<char>(__c)); } //@} //@{ /** * @brief String inserters * @param __out An output stream. * @param __s A character string. * @return out * @pre @p __s must be a non-NULL pointer * * Behaves like one of the formatted arithmetic inserters described in * std::basic_ostream. After constructing a sentry object with good * status, this function inserts @c traits::length(__s) characters starting * at @p __s, widened if necessary, followed by any required padding (as * determined by [22.2.2.2.2]). @c __out.width(0) is then called. */ template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s) { if (!__s) __out.setstate(ios_base::badbit); else __ostream_insert(__out, __s, static_cast<streamsize>(_Traits::length(__s))); return __out; } template<typename _CharT, typename _Traits> basic_ostream<_CharT, _Traits> & operator<<(basic_ostream<_CharT, _Traits>& __out, const char* __s); // Partial specializations template<class _Traits> inline basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& __out, const char* __s) { if (!__s) __out.setstate(ios_base::badbit); else __ostream_insert(__out, __s, static_cast<streamsize>(_Traits::length(__s))); return __out; } // Signed and unsigned template<class _Traits> inline basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& __out, const signed char* __s) { return (__out << reinterpret_cast<const char*>(__s)); } template<class _Traits> inline basic_ostream<char, _Traits> & operator<<(basic_ostream<char, _Traits>& __out, const unsigned char* __s) { return (__out << reinterpret_cast<const char*>(__s)); } //@} // Standard basic_ostream manipulators /** * @brief Write a newline and flush the stream. * * This manipulator is often mistakenly used when a simple newline is * desired, leading to poor buffering performance. See * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt11ch25s02.html * for more on this subject. */ template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& endl(basic_ostream<_CharT, _Traits>& __os) { return flush(__os.put(__os.widen('\n'))); } /** * @brief Write a null character into the output sequence. * * <em>Null character</em> is @c CharT() by definition. For CharT * of @c char, this correctly writes the ASCII @c NUL character * string terminator. */ template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& ends(basic_ostream<_CharT, _Traits>& __os) { return __os.put(_CharT()); } /** * @brief Flushes the output stream. * * This manipulator simply calls the stream's @c flush() member function. */ template<typename _CharT, typename _Traits> inline basic_ostream<_CharT, _Traits>& flush(basic_ostream<_CharT, _Traits>& __os) { return __os.flush(); } #if __cplusplus >= 201103L /** * @brief Generic inserter for rvalue stream * @param __os An input stream. * @param __x A reference to the object being inserted. * @return os * * This is just a forwarding function to allow insertion to * rvalue streams since they won't bind to the inserter functions * that take an lvalue reference. */ template<typename _CharT, typename _Traits, typename _Tp> inline basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>&& __os, const _Tp& __x) { return (__os << __x); } #endif // C++11 _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #include <bits/ostream.tcc> #endif /* _GLIBCXX_OSTREAM */ #ifndef _GLIBCXX_ISTREAM #define _GLIBCXX_ISTREAM 1 #pragma GCC system_header #include <ios> #include <ostream> namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * @brief Template class basic_istream. * @ingroup io * * @tparam _CharT Type of character stream. * @tparam _Traits Traits for character type, defaults to * char_traits<_CharT>. * * This is the base class for all input streams. It provides text * formatting of all builtin types, and communicates with any class * derived from basic_streambuf to do the actual input. */ template<typename _CharT, typename _Traits> class basic_istream : virtual public basic_ios<_CharT, _Traits> { public: // Types (inherited from basic_ios (27.4.4)): typedef _CharT char_type; typedef typename _Traits::int_type int_type; typedef typename _Traits::pos_type pos_type; typedef typename _Traits::off_type off_type; typedef _Traits traits_type; // Non-standard Types: typedef basic_streambuf<_CharT, _Traits> __streambuf_type; typedef basic_ios<_CharT, _Traits> __ios_type; typedef basic_istream<_CharT, _Traits> __istream_type; typedef num_get<_CharT, istreambuf_iterator<_CharT, _Traits> > __num_get_type; typedef ctype<_CharT> __ctype_type; protected: // Data Members: /** * The number of characters extracted in the previous unformatted * function; see gcount(). */ streamsize _M_gcount; public: /** * @brief Base constructor. * * This ctor is almost never called by the user directly, rather from * derived classes' initialization lists, which pass a pointer to * their own stream buffer. */ explicit basic_istream(__streambuf_type* __sb) : _M_gcount(streamsize(0)) { this->init(__sb); } /** * @brief Base destructor. * * This does very little apart from providing a virtual base dtor. */ virtual ~basic_istream() { _M_gcount = streamsize(0); } /// Safe prefix/suffix operations. class sentry; friend class sentry; //@{ /** * @brief Interface for manipulators. * * Manipulators such as @c std::ws and @c std::dec use these * functions in constructs like * <code>std::cin >> std::ws</code>. * For more information, see the iomanip header. */ __istream_type& operator>>(__istream_type& (*__pf)(__istream_type&)) { return __pf(*this); } __istream_type& operator>>(__ios_type& (*__pf)(__ios_type&)) { __pf(*this); return *this; } __istream_type& operator>>(ios_base& (*__pf)(ios_base&)) { __pf(*this); return *this; } //@} //@{ /** * @name Extractors * * All the @c operator>> functions (aka <em>formatted input * functions</em>) have some common behavior. Each starts by * constructing a temporary object of type std::basic_istream::sentry * with the second argument (noskipws) set to false. This has several * effects, concluding with the setting of a status flag; see the * sentry documentation for more. * * If the sentry status is good, the function tries to extract * whatever data is appropriate for the type of the argument. * * If an exception is thrown during extraction, ios_base::badbit * will be turned on in the stream's error state without causing an * ios_base::failure to be thrown. The original exception will then * be rethrown. */ //@{ /** * @brief Integer arithmetic extractors * @param __n A variable of builtin integral type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to parse the input data. */ __istream_type& operator>>(bool& __n) { return _M_extract(__n); } __istream_type& operator>>(short& __n); __istream_type& operator>>(unsigned short& __n) { return _M_extract(__n); } __istream_type& operator>>(int& __n); __istream_type& operator>>(unsigned int& __n) { return _M_extract(__n); } __istream_type& operator>>(long& __n) { return _M_extract(__n); } __istream_type& operator>>(unsigned long& __n) { return _M_extract(__n); } #ifdef _GLIBCXX_USE_LONG_LONG __istream_type& operator>>(long long& __n) { return _M_extract(__n); } __istream_type& operator>>(unsigned long long& __n) { return _M_extract(__n); } #endif //@} //@{ /** * @brief Floating point arithmetic extractors * @param __f A variable of builtin floating point type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to parse the input data. */ __istream_type& operator>>(float& __f) { return _M_extract(__f); } __istream_type& operator>>(double& __f) { return _M_extract(__f); } __istream_type& operator>>(long double& __f) { return _M_extract(__f); } //@} /** * @brief Basic arithmetic extractors * @param __p A variable of pointer type. * @return @c *this if successful * * These functions use the stream's current locale (specifically, the * @c num_get facet) to parse the input data. */ __istream_type& operator>>(void*& __p) { return _M_extract(__p); } /** * @brief Extracting into another streambuf. * @param __sb A pointer to a streambuf * * This function behaves like one of the basic arithmetic extractors, * in that it also constructs a sentry object and has the same error * handling behavior. * * If @p __sb is NULL, the stream will set failbit in its error state. * * Characters are extracted from this stream and inserted into the * @p __sb streambuf until one of the following occurs: * * - the input stream reaches end-of-file, * - insertion into the output buffer fails (in this case, the * character that would have been inserted is not extracted), or * - an exception occurs (and in this case is caught) * * If the function inserts no characters, failbit is set. */ __istream_type& operator>>(__streambuf_type* __sb); //@} // [27.6.1.3] unformatted input /** * @brief Character counting * @return The number of characters extracted by the previous * unformatted input function dispatched for this stream. */ streamsize gcount() const { return _M_gcount; } //@{ /** * @name Unformatted Input Functions * * All the unformatted input functions have some common behavior. * Each starts by constructing a temporary object of type * std::basic_istream::sentry with the second argument (noskipws) * set to true. This has several effects, concluding with the * setting of a status flag; see the sentry documentation for more. * * If the sentry status is good, the function tries to extract * whatever data is appropriate for the type of the argument. * * The number of characters extracted is stored for later retrieval * by gcount(). * * If an exception is thrown during extraction, ios_base::badbit * will be turned on in the stream's error state without causing an * ios_base::failure to be thrown. The original exception will then * be rethrown. */ /** * @brief Simple extraction. * @return A character, or eof(). * * Tries to extract a character. If none are available, sets failbit * and returns traits::eof(). */ int_type get(); /** * @brief Simple extraction. * @param __c The character in which to store data. * @return *this * * Tries to extract a character and store it in @a __c. If none are * available, sets failbit and returns traits::eof(). * * @note This function is not overloaded on signed char and * unsigned char. */ __istream_type& get(char_type& __c); /** * @brief Simple multiple-character extraction. * @param __s Pointer to an array. * @param __n Maximum number of characters to store in @a __s. * @param __delim A "stop" character. * @return *this * * Characters are extracted and stored into @a __s until one of the * following happens: * * - @c __n-1 characters are stored * - the input sequence reaches EOF * - the next character equals @a __delim, in which case the character * is not extracted * * If no characters are stored, failbit is set in the stream's error * state. * * In any case, a null character is stored into the next location in * the array. * * @note This function is not overloaded on signed char and * unsigned char. */ __istream_type& get(char_type* __s, streamsize __n, char_type __delim); /** * @brief Simple multiple-character extraction. * @param __s Pointer to an array. * @param __n Maximum number of characters to store in @a s. * @return *this * * Returns @c get(__s,__n,widen('\\n')). */ __istream_type& get(char_type* __s, streamsize __n) { return this->get(__s, __n, this->widen('\n')); } /** * @brief Extraction into another streambuf. * @param __sb A streambuf in which to store data. * @param __delim A "stop" character. * @return *this * * Characters are extracted and inserted into @a __sb until one of the * following happens: * * - the input sequence reaches EOF * - insertion into the output buffer fails (in this case, the * character that would have been inserted is not extracted) * - the next character equals @a __delim (in this case, the character * is not extracted) * - an exception occurs (and in this case is caught) * * If no characters are stored, failbit is set in the stream's error * state. */ __istream_type& get(__streambuf_type& __sb, char_type __delim); /** * @brief Extraction into another streambuf. * @param __sb A streambuf in which to store data. * @return *this * * Returns @c get(__sb,widen('\\n')). */ __istream_type& get(__streambuf_type& __sb) { return this->get(__sb, this->widen('\n')); } /** * @brief String extraction. * @param __s A character array in which to store the data. * @param __n Maximum number of characters to extract. * @param __delim A "stop" character. * @return *this * * Extracts and stores characters into @a __s until one of the * following happens. Note that these criteria are required to be * tested in the order listed here, to allow an input line to exactly * fill the @a __s array without setting failbit. * * -# the input sequence reaches end-of-file, in which case eofbit * is set in the stream error state * -# the next character equals @c __delim, in which case the character * is extracted (and therefore counted in @c gcount()) but not stored * -# @c __n-1 characters are stored, in which case failbit is set * in the stream error state * * If no characters are extracted, failbit is set. (An empty line of * input should therefore not cause failbit to be set.) * * In any case, a null character is stored in the next location in * the array. */ __istream_type& getline(char_type* __s, streamsize __n, char_type __delim); /** * @brief String extraction. * @param __s A character array in which to store the data. * @param __n Maximum number of characters to extract. * @return *this * * Returns @c getline(__s,__n,widen('\\n')). */ __istream_type& getline(char_type* __s, streamsize __n) { return this->getline(__s, __n, this->widen('\n')); } /** * @brief Discarding characters * @param __n Number of characters to discard. * @param __delim A "stop" character. * @return *this * * Extracts characters and throws them away until one of the * following happens: * - if @a __n @c != @c std::numeric_limits<int>::max(), @a __n * characters are extracted * - the input sequence reaches end-of-file * - the next character equals @a __delim (in this case, the character * is extracted); note that this condition will never occur if * @a __delim equals @c traits::eof(). * * NB: Provide three overloads, instead of the single function * (with defaults) mandated by the Standard: this leads to a * better performing implementation, while still conforming to * the Standard. */ __istream_type& ignore(streamsize __n, int_type __delim); __istream_type& ignore(streamsize __n); __istream_type& ignore(); /** * @brief Looking ahead in the stream * @return The next character, or eof(). * * If, after constructing the sentry object, @c good() is false, * returns @c traits::eof(). Otherwise reads but does not extract * the next input character. */ int_type peek(); /** * @brief Extraction without delimiters. * @param __s A character array. * @param __n Maximum number of characters to store. * @return *this * * If the stream state is @c good(), extracts characters and stores * them into @a __s until one of the following happens: * - @a __n characters are stored * - the input sequence reaches end-of-file, in which case the error * state is set to @c failbit|eofbit. * * @note This function is not overloaded on signed char and * unsigned char. */ __istream_type& read(char_type* __s, streamsize __n); /** * @brief Extraction until the buffer is exhausted, but no more. * @param __s A character array. * @param __n Maximum number of characters to store. * @return The number of characters extracted. * * Extracts characters and stores them into @a __s depending on the * number of characters remaining in the streambuf's buffer, * @c rdbuf()->in_avail(), called @c A here: * - if @c A @c == @c -1, sets eofbit and extracts no characters * - if @c A @c == @c 0, extracts no characters * - if @c A @c > @c 0, extracts @c min(A,n) * * The goal is to empty the current buffer, and to not request any * more from the external input sequence controlled by the streambuf. */ streamsize readsome(char_type* __s, streamsize __n); /** * @brief Unextracting a single character. * @param __c The character to push back into the input stream. * @return *this * * If @c rdbuf() is not null, calls @c rdbuf()->sputbackc(c). * * If @c rdbuf() is null or if @c sputbackc() fails, sets badbit in * the error state. * * @note This function first clears eofbit. Since no characters * are extracted, the next call to @c gcount() will return 0, * as required by DR 60. */ __istream_type& putback(char_type __c); /** * @brief Unextracting the previous character. * @return *this * * If @c rdbuf() is not null, calls @c rdbuf()->sungetc(c). * * If @c rdbuf() is null or if @c sungetc() fails, sets badbit in * the error state. * * @note This function first clears eofbit. Since no characters * are extracted, the next call to @c gcount() will return 0, * as required by DR 60. */ __istream_type& unget(); /** * @brief Synchronizing the stream buffer. * @return 0 on success, -1 on failure * * If @c rdbuf() is a null pointer, returns -1. * * Otherwise, calls @c rdbuf()->pubsync(), and if that returns -1, * sets badbit and returns -1. * * Otherwise, returns 0. * * @note This function does not count the number of characters * extracted, if any, and therefore does not affect the next * call to @c gcount(). */ int sync(); /** * @brief Getting the current read position. * @return A file position object. * * If @c fail() is not false, returns @c pos_type(-1) to indicate * failure. Otherwise returns @c rdbuf()->pubseekoff(0,cur,in). * * @note This function does not count the number of characters * extracted, if any, and therefore does not affect the next * call to @c gcount(). At variance with putback, unget and * seekg, eofbit is not cleared first. */ pos_type tellg(); /** * @brief Changing the current read position. * @param __pos A file position object. * @return *this * * If @c fail() is not true, calls @c rdbuf()->pubseekpos(__pos). If * that function fails, sets failbit. * * @note This function first clears eofbit. It does not count the * number of characters extracted, if any, and therefore does * not affect the next call to @c gcount(). */ __istream_type& seekg(pos_type); /** * @brief Changing the current read position. * @param __off A file offset object. * @param __dir The direction in which to seek. * @return *this * * If @c fail() is not true, calls @c rdbuf()->pubseekoff(__off,__dir). * If that function fails, sets failbit. * * @note This function first clears eofbit. It does not count the * number of characters extracted, if any, and therefore does * not affect the next call to @c gcount(). */ __istream_type& seekg(off_type, ios_base::seekdir); //@} protected: basic_istream() : _M_gcount(streamsize(0)) { this->init(0); } template<typename _ValueT> __istream_type& _M_extract(_ValueT& __v); }; /// Explicit specialization declarations, defined in src/istream.cc. template<> basic_istream<char>& basic_istream<char>:: getline(char_type* __s, streamsize __n, char_type __delim); template<> basic_istream<char>& basic_istream<char>:: ignore(streamsize __n); template<> basic_istream<char>& basic_istream<char>:: ignore(streamsize __n, int_type __delim); #ifdef _GLIBCXX_USE_WCHAR_T template<> basic_istream<wchar_t>& basic_istream<wchar_t>:: getline(char_type* __s, streamsize __n, char_type __delim); template<> basic_istream<wchar_t>& basic_istream<wchar_t>:: ignore(streamsize __n); template<> basic_istream<wchar_t>& basic_istream<wchar_t>:: ignore(streamsize __n, int_type __delim); #endif /** * @brief Performs setup work for input streams. * * Objects of this class are created before all of the standard * extractors are run. It is responsible for <em>exception-safe * prefix and suffix operations,</em> although only prefix actions * are currently required by the standard. */ template<typename _CharT, typename _Traits> class basic_istream<_CharT, _Traits>::sentry { // Data Members. bool _M_ok; public: /// Easy access to dependent types. typedef _Traits traits_type; typedef basic_streambuf<_CharT, _Traits> __streambuf_type; typedef basic_istream<_CharT, _Traits> __istream_type; typedef typename __istream_type::__ctype_type __ctype_type; typedef typename _Traits::int_type __int_type; /** * @brief The constructor performs all the work. * @param __is The input stream to guard. * @param __noskipws Whether to consume whitespace or not. * * If the stream state is good (@a __is.good() is true), then the * following actions are performed, otherwise the sentry state * is false (<em>not okay</em>) and failbit is set in the * stream state. * * The sentry's preparatory actions are: * * -# if the stream is tied to an output stream, @c is.tie()->flush() * is called to synchronize the output sequence * -# if @a __noskipws is false, and @c ios_base::skipws is set in * @c is.flags(), the sentry extracts and discards whitespace * characters from the stream. The currently imbued locale is * used to determine whether each character is whitespace. * * If the stream state is still good, then the sentry state becomes * true (@a okay). */ explicit sentry(basic_istream<_CharT, _Traits>& __is, bool __noskipws = false); /** * @brief Quick status checking. * @return The sentry state. * * For ease of use, sentries may be converted to booleans. The * return value is that of the sentry state (true == okay). */ #if __cplusplus >= 201103L explicit #endif operator bool() const { return _M_ok; } }; //@{ /** * @brief Character extractors * @param __in An input stream. * @param __c A character reference. * @return in * * Behaves like one of the formatted arithmetic extractors described in * std::basic_istream. After constructing a sentry object with good * status, this function extracts a character (if one is available) and * stores it in @a __c. Otherwise, sets failbit in the input stream. */ template<typename _CharT, typename _Traits> basic_istream<_CharT, _Traits>& operator>>(basic_istream<_CharT, _Traits>& __in, _CharT& __c); template<class _Traits> inline basic_istream<char, _Traits>& operator>>(basic_istream<char, _Traits>& __in, unsigned char& __c) { return (__in >> reinterpret_cast<char&>(__c)); } template<class _Traits> inline basic_istream<char, _Traits>& operator>>(basic_istream<char, _Traits>& __in, signed char& __c) { return (__in >> reinterpret_cast<char&>(__c)); } //@} //@{ /** * @brief Character string extractors * @param __in An input stream. * @param __s A pointer to a character array. * @return __in * * Behaves like one of the formatted arithmetic extractors described in * std::basic_istream. After constructing a sentry object with good * status, this function extracts up to @c n characters and stores them * into the array starting at @a __s. @c n is defined as: * * - if @c width() is greater than zero, @c n is width() otherwise * - @c n is <em>the number of elements of the largest array of * * - @c char_type that can store a terminating @c eos.</em> * - [27.6.1.2.3]/6 * * Characters are extracted and stored until one of the following happens: * - @c n-1 characters are stored * - EOF is reached * - the next character is whitespace according to the current locale * - the next character is a null byte (i.e., @c charT() ) * * @c width(0) is then called for the input stream. * * If no characters are extracted, sets failbit. */ template<typename _CharT, typename _Traits> basic_istream<_CharT, _Traits>& operator>>(basic_istream<_CharT, _Traits>& __in, _CharT* __s); // Explicit specialization declaration, defined in src/istream.cc. template<> basic_istream<char>& operator>>(basic_istream<char>& __in, char* __s); template<class _Traits> inline basic_istream<char, _Traits>& operator>>(basic_istream<char, _Traits>& __in, unsigned char* __s) { return (__in >> reinterpret_cast<char*>(__s)); } template<class _Traits> inline basic_istream<char, _Traits>& operator>>(basic_istream<char, _Traits>& __in, signed char* __s) { return (__in >> reinterpret_cast<char*>(__s)); } //@} /** * @brief Template class basic_iostream * @ingroup io * * @tparam _CharT Type of character stream. * @tparam _Traits Traits for character type, defaults to * char_traits<_CharT>. * * This class multiply inherits from the input and output stream classes * simply to provide a single interface. */ template<typename _CharT, typename _Traits> class basic_iostream : public basic_istream<_CharT, _Traits>, public basic_ostream<_CharT, _Traits> { public: // _GLIBCXX_RESOLVE_LIB_DEFECTS // 271. basic_iostream missing typedefs // Types (inherited): typedef _CharT char_type; typedef typename _Traits::int_type int_type; typedef typename _Traits::pos_type pos_type; typedef typename _Traits::off_type off_type; typedef _Traits traits_type; // Non-standard Types: typedef basic_istream<_CharT, _Traits> __istream_type; typedef basic_ostream<_CharT, _Traits> __ostream_type; /** * @brief Constructor does nothing. * * Both of the parent classes are initialized with the same * streambuf pointer passed to this constructor. */ explicit basic_iostream(basic_streambuf<_CharT, _Traits>* __sb) : __istream_type(__sb), __ostream_type(__sb) { } /** * @brief Destructor does nothing. */ virtual ~basic_iostream() { } protected: basic_iostream() : __istream_type(), __ostream_type() { } }; /** * @brief Quick and easy way to eat whitespace * * This manipulator extracts whitespace characters, stopping when the * next character is non-whitespace, or when the input sequence is empty. * If the sequence is empty, @c eofbit is set in the stream, but not * @c failbit. * * The current locale is used to distinguish whitespace characters. * * Example: * @code * MyClass mc; * * std::cin >> std::ws >> mc; * @endcode * will skip leading whitespace before calling operator>> on cin and your * object. Note that the same effect can be achieved by creating a * std::basic_istream::sentry inside your definition of operator>>. */ template<typename _CharT, typename _Traits> basic_istream<_CharT, _Traits>& ws(basic_istream<_CharT, _Traits>& __is); #if __cplusplus >= 201103L // [27.7.1.6] Rvalue stream extraction /** * @brief Generic extractor for rvalue stream * @param __is An input stream. * @param __x A reference to the extraction target. * @return is * * This is just a forwarding function to allow extraction from * rvalue streams since they won't bind to the extractor functions * that take an lvalue reference. */ template<typename _CharT, typename _Traits, typename _Tp> inline basic_istream<_CharT, _Traits>& operator>>(basic_istream<_CharT, _Traits>&& __is, _Tp& __x) { return (__is >> __x); } #endif // C++11 _GLIBCXX_END_NAMESPACE_VERSION } // namespace #include <bits/istream.tcc> #endif /* _GLIBCXX_ISTREAM */ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * @name Standard Stream Objects * * The <iostream> header declares the eight <em>standard stream * objects</em>. For other declarations, see * http://gcc.gnu.org/onlinedocs/libstdc++/manual/io.html * and the @link iosfwd I/O forward declarations @endlink * * They are required by default to cooperate with the global C * library's @c FILE streams, and to be available during program * startup and termination. For more information, see the section of the * manual linked to above. */ //@{ extern istream cin; /// Linked to standard input extern ostream cout; /// Linked to standard output extern ostream cerr; /// Linked to standard error (unbuffered) extern ostream clog; /// Linked to standard error (buffered) #ifdef _GLIBCXX_USE_WCHAR_T extern wistream wcin; /// Linked to standard input extern wostream wcout; /// Linked to standard output extern wostream wcerr; /// Linked to standard error (unbuffered) extern wostream wclog; /// Linked to standard error (buffered) #endif //@} // For construction of filebuffers for cout, cin, cerr, clog et. al. static ios_base::Init __ioinit; _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif #ifndef _GLIBCXX_ALGORITHM #define _GLIBCXX_ALGORITHM 1 #pragma GCC system_header #ifndef _GLIBCXX_UTILITY #define _GLIBCXX_UTILITY 1 #pragma GCC system_header /** * @defgroup utilities Utilities * * Components deemed generally useful. Includes pair, tuple, * forward/move helpers, ratio, function object, metaprogramming and * type traits, time, date, and memory functions. */ #include <bits/c++config.h> #include <bits/stl_relops.h> #include <bits/stl_pair.h> #if __cplusplus >= 201103L #include <bits/move.h> #include <initializer_list> namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION template<class _Tp> class tuple_size; template<std::size_t _Int, class _Tp> class tuple_element; // Various functions which give std::pair a tuple-like interface. template<class _Tp1, class _Tp2> struct tuple_size<std::pair<_Tp1, _Tp2>> : public integral_constant<std::size_t, 2> { }; template<class _Tp1, class _Tp2> struct tuple_element<0, std::pair<_Tp1, _Tp2>> { typedef _Tp1 type; }; template<class _Tp1, class _Tp2> struct tuple_element<1, std::pair<_Tp1, _Tp2>> { typedef _Tp2 type; }; template<std::size_t _Int> struct __pair_get; template<> struct __pair_get<0> { template<typename _Tp1, typename _Tp2> static constexpr _Tp1& __get(std::pair<_Tp1, _Tp2>& __pair) noexcept { return __pair.first; } template<typename _Tp1, typename _Tp2> static constexpr _Tp1&& __move_get(std::pair<_Tp1, _Tp2>&& __pair) noexcept { return std::forward<_Tp1>(__pair.first); } template<typename _Tp1, typename _Tp2> static constexpr const _Tp1& __const_get(const std::pair<_Tp1, _Tp2>& __pair) noexcept { return __pair.first; } }; template<> struct __pair_get<1> { template<typename _Tp1, typename _Tp2> static constexpr _Tp2& __get(std::pair<_Tp1, _Tp2>& __pair) noexcept { return __pair.second; } template<typename _Tp1, typename _Tp2> static constexpr _Tp2&& __move_get(std::pair<_Tp1, _Tp2>&& __pair) noexcept { return std::forward<_Tp2>(__pair.second); } template<typename _Tp1, typename _Tp2> static constexpr const _Tp2& __const_get(const std::pair<_Tp1, _Tp2>& __pair) noexcept { return __pair.second; } }; template<std::size_t _Int, class _Tp1, class _Tp2> constexpr typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type& get(std::pair<_Tp1, _Tp2>& __in) noexcept { return __pair_get<_Int>::__get(__in); } template<std::size_t _Int, class _Tp1, class _Tp2> constexpr typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type&& get(std::pair<_Tp1, _Tp2>&& __in) noexcept { return __pair_get<_Int>::__move_get(std::move(__in)); } template<std::size_t _Int, class _Tp1, class _Tp2> constexpr const typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type& get(const std::pair<_Tp1, _Tp2>& __in) noexcept { return __pair_get<_Int>::__const_get(__in); } #if __cplusplus > 201103L #define __cpp_lib_tuples_by_type 201304 template <typename _Tp, typename _Up> constexpr _Tp& get(pair<_Tp, _Up>& __p) noexcept { return __p.first; } template <typename _Tp, typename _Up> constexpr const _Tp& get(const pair<_Tp, _Up>& __p) noexcept { return __p.first; } template <typename _Tp, typename _Up> constexpr _Tp&& get(pair<_Tp, _Up>&& __p) noexcept { return std::move(__p.first); } template <typename _Tp, typename _Up> constexpr _Tp& get(pair<_Up, _Tp>& __p) noexcept { return __p.second; } template <typename _Tp, typename _Up> constexpr const _Tp& get(const pair<_Up, _Tp>& __p) noexcept { return __p.second; } template <typename _Tp, typename _Up> constexpr _Tp&& get(pair<_Up, _Tp>&& __p) noexcept { return std::move(__p.second); } #define __cpp_lib_exchange_function 201304 /// Assign @p __new_val to @p __obj and return its previous value. template <typename _Tp, typename _Up = _Tp> inline _Tp exchange(_Tp& __obj, _Up&& __new_val) { _Tp __old_val = std::move(__obj); __obj = std::forward<_Up>(__new_val); return __old_val; } #endif // Stores a tuple of indices. Used by tuple and pair, and by bind() to // extract the elements in a tuple. template<size_t... _Indexes> struct _Index_tuple { typedef _Index_tuple<_Indexes..., sizeof...(_Indexes)> __next; }; // Builds an _Index_tuple<0, 1, 2, ..., _Num-1>. template<size_t _Num> struct _Build_index_tuple { typedef typename _Build_index_tuple<_Num - 1>::__type::__next __type; }; template<> struct _Build_index_tuple<0> { typedef _Index_tuple<> __type; }; #if __cplusplus > 201103L #define __cpp_lib_integer_sequence 201304 /// Class template integer_sequence template<typename _Tp, _Tp... _Idx> struct integer_sequence { typedef _Tp value_type; static constexpr size_t size() { return sizeof...(_Idx); } }; template<typename _Tp, _Tp _Num, typename _ISeq = typename _Build_index_tuple<_Num>::__type> struct _Make_integer_sequence; template<typename _Tp, _Tp _Num, size_t... _Idx> struct _Make_integer_sequence<_Tp, _Num, _Index_tuple<_Idx...>> { static_assert( _Num >= 0, "Cannot make integer sequence of negative length" ); typedef integer_sequence<_Tp, static_cast<_Tp>(_Idx)...> __type; }; /// Alias template make_integer_sequence template<typename _Tp, _Tp _Num> using make_integer_sequence = typename _Make_integer_sequence<_Tp, _Num>::__type; /// Alias template index_sequence template<size_t... _Idx> using index_sequence = integer_sequence<size_t, _Idx...>; /// Alias template make_index_sequence template<size_t _Num> using make_index_sequence = make_integer_sequence<size_t, _Num>; /// Alias template index_sequence_for template<typename... _Types> using index_sequence_for = make_index_sequence<sizeof...(_Types)>; #endif _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif #endif /* _GLIBCXX_UTILITY */ #include <bits/stl_algobase.h> #include <bits/stl_algo.h> #ifdef _GLIBCXX_PARALLEL # include <parallel/algorithm> #endif #endif using namespace std; struct road{ long long u; long long v; long long c; }; road e[100005]; long long n; long long father[100005]; long long ans=0; long long pre[100005]; long long cmp(road a,road b){return a.c<b.c;} long long find(long long x){return father[x]==x?x:father[x]=find(father[x]);} /* void bing(long long x,long long y) { long long fx=find(x); long long fy=find(y); if(fx!=fy) father[fy]=fx; } */ void kru(){for(long long i=1;i<n;i++){long long fa=find(e[i].u),fb=find(e[i].v);if(fa!=fb)ans+=e[i].c+(e[i].c+1)*(pre[fa]*pre[fb]-1),father[fa]=fb,pre[fb]+=pre[fa];}} int main() { cin>>n; for(long long i=1;i<n;i++) cin>>e[i].u>>e[i].v>>e[i].c; sort(e+1,e+n,cmp); for(long long i=1;i<=n;i++) father[i]=i,pre[i]=1; kru(); cout<<ans; return 0; }-
Rssqzqyp @ 2017-09-19 16:26:40
铁一果然zz多
-
qizs @ 2017-10-07 12:04:36
铁一果然你爸多
-
Administrator2004 @ 2017-10-08 13:45:01
铁一果然你爸多
-
-
-3
larryzhong LV 9 @ 2017-05-08 21:04:13
kruskal:
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct edge { int from, to, cost; edge(int u, int v, int c) : from(u), to(v), cost(c) {} bool operator < (const edge &other) const { return cost < other.cost; } }; const int maxn = 100010; int n, father[maxn], size[maxn]; vector<edge> G; void init() { for (int i = 1; i <= n; i++) { father[i] = i; size[i] = 1; } } int find(int x) { if (x == father[x]) return x; else { father[x] = find(father[x]); size[x] = size[father[x]]; return father[x]; } } void unite(int x, int y) { x = find(x); y = find(y); father[x] = y; size[y] += size[x]; } long long kruskal() { sort(G.begin(), G.end()); long long res = 0; for (int i = 0; i < n - 1; i++) { int x = find(G[i].from), y = find(G[i].to); res += (long long)G[i].cost + (long long)(size[x] * size[y] - 1) * (long long)(G[i].cost + 1); unite(x, y); } return res; } int main() { cin >> n; for (int i = 1; i < n; i++) { int from, to, cost; cin >> from >> to >> cost; G.push_back(edge(from, to, cost)); } init(); cout << kruskal() << endl; return 0; } -
-3
#include <cstdio>
#include <iostream>
#include <algorithm>struct PIGFF{
int s1,s2;
long long val;
}a[20010];int n,pre[20010];
long long sum[20010];int find(int x){
if(x!=pre[x])
pre[x]=find(pre[x]);
return pre[x];
}int join(int x,int y){
int pa=find(x);
int pb=find(y);
pre[pb]=pa;
sum[pa]+=sum[pb];
}bool LYB(PIGFF a,PIGFF b){
return a.val<b.val;
}int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
sum[i]=1,pre[i]=i;
for(int i=1;i<=n-1;i++){
int s1,s2;
long long val;
scanf("%d%d",&s1,&s2);
std::cin>>val;
a[i].s1=s1,a[i].s2=s2,a[i].val=val;
}
long long ans=0,val;
std::sort(a+1,a+n,LYB);
for(int i=1;i<=n-1;i++){
val=a[i].val;
ans+=val+(val+1)*(sum[find(a[i].s1)]*sum[find(a[i].s2)]-1);
join(a[i].s1,a[i].s2);
}
std::cout<<ans;
return 0;
} -
-3
2641759526 LV 8 @ 2014-02-10 11:13:34
很好的一道题嘛~~
WA了3次，过了。
题解+AC代码
xzp
LV 6
@ 2017-06-10 14:28:46
